SPOJ LCS (접미사 자동 동기)

(http://acm.hust.edu.cn/vjudge/contest/view.action?cid=106071#problem/A) 제목: 꼬치 A, B 의 가장 생김새 와 하위 꼬치 해법: A 의 접미사 자동 동 기 를 직접 구성 하여 lcp 를 만 들 면 된다.

#include 
#include 
#include 
#include 
#include 
#include 
#include 
#include 
#include 
#include 
#include 
#include 
//#include 
#include 
//#pragma comment(linker, "/STACK:1024000000,1024000000")

using namespace std;

#define lson l, m, ls[rt]
#define rson m+1, r, rs[rt]
#define inf 1e9
#define debug(a) cout << #a" = " << (a) << endl;
#define debugarry(a, n) for (int i = 0; i < (n); i++) { cout << #a"[" << i << "] = " << (a)[i] << endl; }
#define clr(x, y) memset(x, y, sizeof x)
#define ll long long
#define ull unsigned long long
#define FOR(i,a,b) \
    for(i=a;a=b;aconst int maxn=2*250000+30;

struct suffix_automaton{
    int son[maxn][30],pre[maxn],step[maxn];
    int last,si;
    void pushback(int v){
        step[++si]=v;
        pre[si]=-1;
        clr(son[si],-1);
    }
    void Extend(int ch)
    {
        pushback(step[last]+1);
        int p=last,np=si;
        while(p!=-1&&son[p][ch]==-1)
            son[p][ch]=np,p=pre[p];
        if(p==-1) pre[np]=0;
        else{
            int q=son[p][ch];
            if(step[q]==step[p]+1) pre[np]=q;
            else{
                pushback(step[p]+1);
                int nq=si;
                memcpy(son[nq],son[q],sizeof son[q]);
                pre[nq]=pre[q];
                pre[q]=pre[np]=nq;
                while(p!=-1&&son[p][ch]==q)
                    son[p][ch]=nq,p=pre[p];
            }
        }
        last=np;
    }
    void init()
    {
        si=last=0;
        clr(son[0],-1);
        pre[0]=-1;
        step[0]=0;
    }
    int lcs(char *s){
        int l=0,ans=0,p=0;
        for(int i=0;s[i];i++){
            int c=s[i]-'a';
            while(p!=-1&&son[p][c]==-1)
                p=pre[p];
            if(p==-1) p=0,l=0;
            else{
                l=min(l,step[p]);
                p=son[p][c];
                l++;
            }
            ans=max(ans,l);
        }
        return ans;
    }
}su;

char s[maxn];

int main()
{
//  freopen("input.txt","r",stdin);
    //freopen("out2.txt","w",stdout);
    while(~scanf("%s",s))
    {
        su.init();
        for(int i=0;s[i];i++)
            su.Extend(s[i]-'a');
        scanf("%s",s);
        printf("%d
",su.lcs(s));
    }
    return 0;
}