@Jerusalem 2015-11-16T09:08:58.000000Z 字数 1798 阅读 1342

### 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;}

• 私有
• 公开
• 删除