AC通道:https://vjudge.net/problem/SPOJ-LCS2
【題解】
我們先把其中一個串建成SAM,然後讓其它的串在SAM上跑,同時更新每個結點的最大比對數。每個結點的答案就是所有串在該結點的最大比對數的最小值。
注意:在更新一個結點時,它的父親必定已經到達過了,要傳回去更新父親的答案。
#include<iostream>
#include<cstdio>
#include<cstdlib>
#include<ctime>
#include<cmath>
#include<cstring>
#include<algorithm>
using namespace std;
#define FILE "read"
#define MAXN 200010
#define up(i,j,n) for(int i=j;i<=n;++i)
#define dn(i,j,n) for(int i=j;i>=n;--i)
#define cmax(a,b) a=max(a,b)
#define cmin(a,b) a=min(a,b)
int n,m,cnt(1),now(1),len(0),mx[MAXN],f[MAXN],c[MAXN],id[MAXN],ans[MAXN],ma[MAXN],son[MAXN][27];
char ch[MAXN];
void insert(int x){
int p=now,np=++cnt;
mx[np]=mx[now]+1; now=np;
while(!son[p][x]&&p) son[p][x]=np,p=f[p];
if(!p) f[np]=1;
else{
int q=son[p][x];
if(mx[q]==mx[p]+1) f[np]=q;
else{
int nq=++cnt;
mx[nq]=mx[p]+1;
memcpy(son[nq],son[q],sizeof(son[q]));
f[nq]=f[q]; f[q]=f[np]=nq;
while(son[p][x]==q) son[p][x]=nq,p=f[p];
}
}
}
void walk(int x){
while(!son[now][x]&&now) now=f[now],len=mx[now];
if(!now) {now=1; len=0; return;}
else now=son[now][x],len++,cmax(ma[now],len);
}
void pre(){
up(i,1,cnt) c[mx[i]]++;
up(i,1,m) c[i]+=c[i-1];
up(i,1,cnt) id[c[mx[i]]--]=i;
up(i,1,cnt) ans[i]=mx[i];
}
int main(){
freopen(FILE".in","r",stdin);
freopen(FILE".out","w",stdout);
scanf("%s",ch+1); m=strlen(ch+1);
up(i,1,m) insert(ch[i]-'a'); pre();
while(scanf("%s",ch+1)!=EOF){
m=strlen(ch+1); now=1; len=0;
up(j,1,m) walk(ch[j]-'a');
dn(j,cnt,1){
int t=id[j];
cmin(ans[t],ma[t]);
if(ma[t]&&f[t]) ma[f[t]]=mx[f[t]];
ma[t]=0;
}
}
up(i,1,cnt) cmax(ans[0],ans[i]);
printf("%d\n",ans[0]);
return 0;
}