spoj Longest Common Substring (多串求最大公共子序列)

#include<bits/stdc++.h>
#define ll long long
using namespace std;
const int maxn=500000*2+7;
char S[maxn];
char S1[maxn/2];
int ans[maxn/2];
int n,a,b,len1,len2;
struct suffixautomation
{
int mp[maxn*2][30],fa[maxn*2],ed,ct,len[maxn*2],minpos[maxn*2],maxpos[maxn*2],deg[maxn*2];
int res[maxn/2];
suffixautomation(){
for(int i=0;i<maxn*2;i++)minpos[i]=1e9,maxpos[i]=-1;
ed=ct=1;}
inline void ins(int c,int pos)
{
int p=ed;ed=++ct;minpos[ed]=maxpos[ed]=pos;len[ed]=pos;//先初始化size和len
for(;p&&mp[p][c]==0;p=fa[p]){mp[p][c]=ed;}//然后顺着parent树的路径向上找
if(p==0){fa[ed]=1;return;}int q=mp[p][c];//case1
if(len[p]+1==len[q]){fa[ed]=q;return;}//case2
len[++ct]=len[p]+1;//case 3
for(int i=1;i<=26;i++){mp[ct][i]=mp[q][i];}
fa[ct]=fa[q];fa[q]=ct;fa[ed]=ct;
for(int i=p;mp[i][c]==q;i=fa[i]){mp[i][c]=ct;}
}
void solve(){ for(int i=1;i<=ct;i++)deg[fa[i]]++;
queue<int>que;
for(int i=1;i<=ct;i++)if(deg[i]==0)que.push(i);
while(que.size()){
int x=que.front();
int y=fa[x];
que.pop();
minpos[y]=min(minpos[x],minpos[y]);
maxpos[y]=max(maxpos[x],maxpos[y]);
deg[y]--;
if(deg[y]==0)que.push(y);
}
for(int i=1;i<=ct;i++)
if(minpos[i]<=len1&&maxpos[i]>=len1+2)
res[minpos[i]]=max(res[minpos[i]],len[i]);
}
}sam,sam2;
int main()
{
// cout<<"acfvd"
for(int i=0;i<maxn/2;i++)ans[i]=1e9;
scanf("%s",S+1);
len1=strlen(S+1);
S[len1+1]='z'+1;
while(scanf("%s",S1+1)==1){
len2=strlen(S1+1);
sam=sam2;
for(int i=len1+2;i<=len1+len2+1;i++)
S[i]=S1[i-len1-1];
for(int i=1;i<=len1+len2+1;i++)sam.ins(S[i]-'a'+1,i);
sam.solve();
for(int i=1;i<=len1;i++)
ans[i]=min(ans[i],sam.res[i]);
}
int res=0;
for(int i=1;i<=len1;i++)
if(ans[i]!=1e9)res=max(res,ans[i]);
printf("%d\n",res);
return 0;
}