【后缀自动机】SPOJ LCS Longest Common Substring

分析：

后缀自动机板子

#include<cstdio>
#include<cstring>
#include<cmath>
#include<vector>
#define SF scanf
#define PF printf
#define MAXN 500010
#define MAXS 30
#define INF 0x3FFFFFFF
using namespace std;
typedef long long ll;
struct node{
    node *fail;node *ch[MAXS];	int len;
}SuA[MAXN],*rt,*ncnt,*last;
void Init(){
    rt=ncnt=last=SuA;	
}
void Insert(char c1){
    int c=c1-'a';node *p=last,*np=++ncnt,*q,*nq;last=np;np->len=p->len+1;while(p&&!p->ch[c])p->ch[c]=np,p=p->fail;if(!p)np->fail=rt;else{
    q=p->ch[c];if(q->len==p->len+1)np->fail=q;else{
    nq=++ncnt;*nq=*q;nq->len=p->len+1;np->fail=q->fail=nq;while(p&&p->ch[c]==q)p->ch[c]=nq,p=p->fail;}}
}
char s[MAXN];
int main(){
    Init();SF("%s",s);int n=strlen(s);last=rt;for(int i=0;i<n;i++)Insert(s[i]);SF("%s",s);n=strlen(s);int ans=0,len=0;node *p=rt;for(int i=0;i<n;i++){
    int c=s[i]-'a';if(p->ch[c]){
    len++;p=p->ch[c];}else{
    while(p&&!p->ch[c])p=p->fail;if(!p)p=rt,len=0;elselen=p->len+1,p=p->ch[c];}ans=max(ans,len);}PF("%d",ans);
}