POJ1743

• 传送门：POJ1743

　　SAM傻逼题。
　　

#include <cstdio>
#include <cstdlib>
#include <cmath>
#include <cstring>
#include <algorithm>
#include <iostream>
using namespace std;
const int maxnode=40005,sigma=180,INF=0x3f3f3f3f;
struct SAM{
    int root,cnt,last;
    int ch[maxnode][sigma]; 
    int Max[maxnode];
    int l[maxnode];
    int r[maxnode];
    int fa[maxnode];
    SAM(){
        root=cnt=last=1;
        memset(ch,0,sizeof(ch));
        memset(Max,0,sizeof(Max));
        memset(fa,0,sizeof(fa));
        memset(l,0,sizeof(l));
        memset(r,0,sizeof(r));
    }
    int newnode(){
        cnt++;
        memset(ch[cnt],0,sizeof(ch[cnt]));
        return cnt;
    }
    void Clear(){
        memset(l,0,sizeof(l));
        memset(r,0,sizeof(r));
        memset(fa,0,sizeof(fa));
        memset(Max,0,sizeof(Max));
        cnt=0;
        last=root=newnode();
    }
    void Insert(int a){
        int p=last;
        int np=newnode();Max[np]=Max[p]+1;l[np]=r[np]=Max[np];
        while(p&&!ch[p][a])
            ch[p][a]=np,p=fa[p];
        if(p==0)
            fa[np]=root;
        else{
            int q=ch[p][a];
            if(Max[q]==Max[p]+1)
                fa[np]=q;
            else{
                int nq=newnode();
                memcpy(ch[nq],ch[q],sizeof(ch[q]));
                l[nq]=INF;r[nq]=0;
                Max[nq]=Max[p]+1;
                fa[nq]=fa[q];
                fa[q]=fa[np]=nq;
                while(p&&ch[p][a]==q)
                    ch[p][a]=nq,p=fa[p];
            }
        }
        last=np;
    }
}; 
SAM Suffix;
int a[maxnode];
int v[maxnode];
int q[maxnode];
int n;
void Solve()
{
    while(cin>>n&&n){
        Suffix.Clear();
        int ans=0;
        for(int i=1;i<=n;i++)
            scanf("%d",&a[i]);
        for(int i=1;i<n;i++)
            a[i]=a[i+1]-a[i]+88;
        for(int i=1;i<n;i++)
            Suffix.Insert(a[i]);
        memset(v,0,sizeof(v));
        for(int i=1;i<=Suffix.cnt;i++)
            v[Suffix.Max[i]]++;
        for(int i=1;i<n;i++)
            v[i]+=v[i-1];
        for(int i=1;i<=Suffix.cnt;i++)
            q[v[Suffix.Max[i]]--]=i;
        for(int i=Suffix.cnt;i>=1;i--){
            int p=q[i];
            Suffix.l[Suffix.fa[p]]=min(Suffix.l[Suffix.fa[p]],Suffix.l[p]);
            Suffix.r[Suffix.fa[p]]=max(Suffix.r[Suffix.fa[p]],Suffix.r[p]);
        }
        for(int i=Suffix.cnt;i>=1;i--)
            ans=max(ans,min(Suffix.Max[i],Suffix.r[i]-Suffix.l[i]));
        cout<<(ans<4?0:ans+1)<<endl;
    }
}
void ReadData()
{
    freopen("POJ1743.in","r",stdin);
}
void Close()
{
    fclose(stdin);
    fclose(stdout);
}
int main()
{
    ReadData();
    Solve();
    Close();
    return 0;
}