WOJ 1084【后缀树】

Gardon - DYGG's contest 4，这题相当恶心，首先你要求出最长出现的连续技的长度，而且是不能重叠的，然后如果有两个连续技的长度是一样的话还要输出那个出现的次数多的那个，很恶心。。很恶心。。

第一次敲后缀树。。。。呼~~~~~~

也许标准的做法是后缀数组吧~~不过我不会

#include<iostream>
#include<algorithm>
#include<vector>
#include<string>
#include<cstdio>
#include<cstring>
#include<cassert>
using namespace std;
const int inf = 0x3f3f3f3f;
const int maxn = 1000001;
const int maxc = 1011;
const int head = 0;

int a[maxc];
int maxlen,sd,ans;

struct zz
{
    int to[20];
    int len;
    int id;
    int re;
    int have;
}zx[maxn];

int use,n;

int get()
{
    use++;
    memset(zx[use].to,-1,sizeof(zx[use].to));
    zx[use].len = 0;
    zx[use].id = 0;
    zx[use].re = -inf;
    zx[use].have = 0;
    return use;
}

void insert(int p)
{
    int now = head;
    int to;
    int c;
    for(int i=p;i<=n;i++)
    {
        c = a[i];
        if(zx[now].to[c] != -1)
        {
            to = zx[now].to[c];
            zx[to].len = zx[now].len+1;
            now = to;
        }
        else
        {
            zx[now].to[c] = get();
            to = zx[now].to[c];
            zx[to].id = p;
            zx[to].len = zx[now].len + 1;
            now = to;
        }
    }
    return ;
}

void find(int p)
{
    int now = head;
    int len = 0;
    int c;
    for(int i=p;i<=n;i++)
    {
        c = a[i];
        now = zx[now].to[c];
        if(zx[now].id > p + len)
        {
            len++;
            if(len > maxlen)
            {
                maxlen = len;
            }
        }
        else
        {
            return ;
        }
    }
    return ;
}

void fk(int p)
{
    int now = head;
    int len = 0;
    int c;
    int temp;
    for(int i=p;i<=n;i++)
    {
        c = a[i];
        now = zx[now].to[c];
        if(zx[now].id > p + len)
        {
            len++;
            if(len == maxlen)
            {
                temp = zx[now].re + maxlen;
                if(p >= temp)
                {
                    zx[now].have++;
                    zx[now].re = p;
                    ans = max(ans,zx[now].have);
                }
                else
                {
                    return ;
                }
            }
        }
        else
        {
            return ;
        }
    }
    return ;
}

void start()
{
    maxlen = -1;
    ans = 0;
    for(int i=n;i>=1;i--)
    {
        insert(i);
    }

    for(int i=1;i<=n;i++)
    {
        find(i);
    }

    if(maxlen == -1)
    {
        cout<<maxlen<<endl;
        return ;
    }

    for(int i=1;i<=n;i++)
    {
        fk(i);
    }

    cout<<maxlen<<" "<<ans+1<<endl;

    return ;
}

int main()
{
    while(cin>>n)
    {
        use = -1;
        get();
        for(int i=1;i<=n;i++)
        {
            cin>>a[i];
            a[i]++;
        }
        start();
    }
    return 0;
}