SPOJ1811最长公共子串问题(后缀自动机)

题目：http://www.spoj.com/problems/LCS/

题意：给两个串A和B，求这两个串的最长公共子串。

分析：其实本题用后缀数组的DC3已经能很好的解决，这里我们来说说利用后缀自动机如何实现。

对于串A和B，我们先构造出串A的后缀自动机，那么然后用B串去匹配，对于B，我们一位一位地扫描，维护一个ans值，表示从

B串的开始到B[i]的这个子串与A的最长公共子串。

假设现在到B[i-1]的最长公共子串长度为ans，然后我们来看B[i]，如果当前节点有B[i]这个孩子，那么直接就len++即可。

如果没有就找一直向前找pre，直到找到有B[i]这个孩子的节点。

#include <iostream>#include <string.h>#include <algorithm>#include <stdio.h>using namespace std;const int N=250005;struct State{    State *pre,*go[26];    int step;    void clear()    {        pre=0;        step=0;        memset(go,0,sizeof(go));    }}*root,*last;State statePool[N*2],*cur;void init(){    cur=statePool;    root=last=cur++;    root->clear();}void Insert(int w){    State *p=last;    State *np=cur++;    np->clear();    np->step=p->step+1;    while(p&&!p->go[w])        p->go[w]=np,p=p->pre;    if(p==0)        np->pre=root;    else    {        State *q=p->go[w];        if(p->step+1==q->step)            np->pre=q;        else        {            State *nq=cur++;            nq->clear();            memcpy(nq->go,q->go,sizeof(q->go));            nq->step=p->step+1;            nq->pre=q->pre;            q->pre=nq;            np->pre=nq;            while(p&&p->go[w]==q)                p->go[w]=nq, p=p->pre;        }    }    last=np;}char A[N],B[N];int main(){    int n,m;    scanf("%s%s",A,B);    n=strlen(A);    m=strlen(B);    init();    for(int i=0; i<n; i++)        Insert(A[i]-'a');    int ans=0,len=0;    State *p=root;    for(int i=0; i<m; i++)    {        int x=B[i]-'a';        if(p->go[x])        {            len++;            p=p->go[x];        }        else        {            while(p&&!p->go[x]) p=p->pre;            if(!p) p=root,len=0;            else   len=p->step+1,p=p->go[x];        }        ans=max(ans,len);    }    printf("%d\n",ans);    return 0;}