POJ2774

• 传送门：POJ2774

　　模板题。
　　
　　但很重要的是：max(trans(s,x))!=max(s)+1，这是因为在状态trans(s,x)，可以抛弃掉状态s的某些Right集合中的点，从而扩大max(trans(s,x))。

#include <cstdio>
#include <cstdlib>
#include <cmath>
#include <cstring>
#include <iostream>
#include <algorithm>
using namespace std;
const int maxnode=200005,sigma=26;
int idx(char a)
{
    return a-'a';
}
struct SAM{
    int root;
    int ch[maxnode][sigma];
    int pa[maxnode];
    int Max[maxnode]; 
    int last;
    int cnt;
    SAM(){
        root=last=cnt=1;
        memset(ch,0,sizeof(ch));
        memset(pa,0,sizeof(pa));
    }
    void Insert(char a){
        int p=last,np=++cnt;
        Max[np]=Max[p]+1;
        while(p&&!ch[p][idx(a)])
            ch[p][idx(a)]=np,p=pa[p];
        if(p==0)
            pa[np]=root;
        else{
            int q=ch[p][idx(a)];
            if(Max[q]==Max[p]+1)
                pa[np]=q;
            else{
                int nq=++cnt;
                memcpy(ch[nq],ch[q],sizeof(ch[nq]));
                Max[nq]=Max[p]+1;
                pa[nq]=pa[q];
                pa[q]=pa[np]=nq;
                while(ch[p][idx(a)]==q){
                    ch[p][idx(a)]=nq;
                    p=pa[p];
                }
            }
        }
        last=np;
    }
};
SAM Suffix;
string P;
void Solve(string S)
{
    int leng=S.length();
    int u=1;
    int len=0,ans=0;
    for(int i=0;i<leng;i++){
        if(Suffix.ch[u][idx(S[i])])
            len++,u=Suffix.ch[u][idx(S[i])];
        else{
            while(u&&!Suffix.ch[u][idx(S[i])])
                u=Suffix.pa[u];
            if(u==0)
                u=1,len=0;
            else
                len=Suffix.Max[u]+1,u=Suffix.ch[u][idx(S[i])];
        }
        ans=max(ans,len);
    }
    cout<<ans<<endl;
}
void ReadData()
{
    cin>>P;
    int len=P.length();
    for(int i=0;i<len;i++)
        Suffix.Insert(P[i]);
    cin>>P;
}
void Close()
{
    fclose(stdin);
    fclose(stdout);
}
int main()
{
    ReadData();
    Solve(P);
    Close();
    return 0;
}