后缀自动机求lcs

spoj lcs.cpp

#include<iostream>
#include<cstdio>
#include<algorithm>
#include<cstring>
using namespace std;
const int N=600000 + 10;
struct SAM{
       SAM* go[26],*fa;
       int l;
}sam[N],*root,*last;
int cur;
char st[N];
inline void expand(int x)
{
     cur++;SAM *p=&sam[cur],*tp=last;p->l=tp->l+1;last=p;
     for(;tp&&!tp->go[x];tp=tp->fa)tp->go[x]=p;
     if(!tp)p->fa=root;
     else if(tp->go[x]->l==tp->l+1)p->fa=tp->go[x];
     else {
          cur++;SAM *q=tp->go[x],*r=&sam[cur];
          *r=*q;
          r->l=tp->l+1;r->fa=q->fa;q->fa=r;p->fa=r;
          for(;tp&&tp->go[x]==q;tp=tp->fa)tp->go[x]=r;
          }
}int ans,no;
SAM *CU;
int main(){
    int n;
    root=&sam[0];last=&sam[0];cur=0;
    scanf("%s",st);n=strlen(st);
    for(int i=0;i<n;i++)expand(st[i]-'a');
    ans=no=0;
    last=root;
    scanf("%s",st);n=strlen(st);
    for(int i=0;i<n;i++)
    {
            st[i]-='a';
            if(last->go[st[i]])
            {
                              no++;
                              last=last->go[st[i]];
            }else{
            for(;last&&!last->go[st[i]];last=last->fa);
            if(!last)last=root,no=0;
            else no=last->l+1,last=last->go[st[i]];
            }ans=max(ans,no);
    }printf("%d\n",ans);return 0;
}