题意
求出多个串的最长公共子串。
分析
刚学SAM想做这个题的话最好先去做一下那道codevs3160。求两个串的LCS应该怎么求？把一个串s1建自动机，然后跑另一个串s2，然后找出s2每个前缀的最长公共后缀。那么多个的时候，我们也用这种类似的方法，但是我们求最长公共后缀的时候要求第一个串的。我们把其中一个串建SAM，然后把其他的串都在上面跑，维护两个值，Max[u]和Min[u]。自动机中每个状态u的Right存的是结尾集合。那么对于一个字符串，我们可以求出他和自动机中每个状态的最长公共后缀。然后，我们通过Max[fa[u]]=max(Max[fa[u]],Max[u])来确定左右状态的最长公共后缀，然后更新Min[o]。
下面的代码没有AC，但是我找了好久BUG没找到··如果有人看完并且找到了bug麻烦跟我说一下万分感谢！
#include <cstdio>
#include <cstring>
#include <iostream>
#include <algorithm> using namespace std;
const int maxn=+;
char s[maxn];
struct state{
int len,link;
int next[];
}st[*maxn];
int n,last,cur,sz;
int Min[*maxn],Max[*maxn],c[*maxn]; void init(){
sz=;
cur=last=;
st[].link=-;
st[].len=;
} void build_sam(int c){
cur=sz++;
st[cur].len=st[last].len+;
Min[cur]=st[cur].len;
int p;
for(p=last;p!=-&&st[p].next[c]==;p=st[p].link)
st[p].next[c]=cur;
if(p==-)
st[cur].link=;
else{
int q=st[p].next[c];
if(st[q].len==st[p].len+)
st[cur].link=q;
else{
int clone=sz++;
st[clone].len=st[p].len+;
Min[clone]=st[clone].len;
st[clone].link=st[q].link;
for(int i=;i<;i++)
st[clone].next[i]=st[q].next[i];
for(;p!=-&&st[p].next[c]==q;p=st[p].link)
st[p].next[c]=clone;
st[cur].link=st[q].link=clone;
}
}
last=cur;
} int cmp(int a,int b){
return st[a].len<st[b].len;
} int main(){
scanf("%s",s);
n=strlen(s);
init(); for(int i=;i<n;i++)
build_sam(s[i]-'a');
for(int i=;i<sz;i++)
c[i]=i;
sort(c,c+sz,cmp); while(scanf("%s",s)!=EOF){
n=strlen(s);
int u=,len=;
for(int i=;i<n;i++){
int c=s[i]-'a';
if(u!=-&&st[u].next[c]==)
u=st[u].link,len=st[u].len;
if(u==-)
u=,len=;
else{
u=st[u].next[c];
len++;
Max[u]=max(Max[u],len);
}
} for(int i=sz-;i>=;i--){
int o=c[i];
Min[o]=min(Min[o],Max[o]);
if(st[o].link!=-){
Max[st[o].link]=max(Max[st[o].link],Max[o]);
}
Max[o]=;
}
}
int ans=;
for(int i=;i<sz;i++){
ans=max(ans,Min[i]);
}
printf("%d\n",ans); return ;
}