http://www.spoj.com/problems/LCS2/ (题目链接)
题意
求多个串的最长公共子串
Solution
对其中一个串构造后缀自动机，然后其它串在上面跑匹配。对于每个串都可以跑出在SAM上的每一个节点的最长公共子串的长度，当然，有些节点虽然匹配时可能没有经过，但是在parent树上它的儿子却被经过了，作为儿子的后缀，那么这些节点显然也是被经过的，所以我们需要用parent树上的儿子节点去更新其父亲节点。完成之后，我们再对全局的匹配长度进行更新（取min）。
爱神：对于SAM初学，要深刻理解出现次数向父亲传递，接收串数从儿子获取这句话。这里的父亲是parent树上的父亲，儿子是SAM图上的后继节点。
代码
// spoj LCS2
#include<algorithm>
#include<iostream>
#include<cstdlib>
#include<cstring>
#include<vector>
#include<cstdio>
#include<cmath>
#include<set>
#define LL long long
#define inf 1<<30
#define Pi acos(-1.0)
#define free(a) freopen(a".in","r",stdin),freopen(a".out","w",stdout);
using namespace std; const int maxn=100010;
char s[maxn]; namespace SAM {
int Dargen,sz,last,n;
int par[maxn<<1],len[maxn<<1],ch[maxn<<1][26],mat[maxn<<1],f[maxn<<1];
int b[maxn],id[maxn<<1];
void Extend(int c) {
int np=++sz,p=last;last=np;
len[np]=len[p]+1;
for (;p && !ch[p][c];p=par[p]) ch[p][c]=np;
if (!p) par[np]=Dargen;
else {
int q=ch[p][c];
if (len[q]==len[p]+1) par[np]=q;
else {
int nq=++sz;len[nq]=len[p]+1;
memcpy(ch[nq],ch[q],sizeof(ch[q]));
par[nq]=par[q];
par[np]=par[q]=nq;
for (;p && ch[p][c]==q;p=par[p]) ch[p][c]=nq;
}
}
}
void build() {
last=sz=Dargen=1;
n=strlen(s+1);
for (int i=1;i<=n;i++) Extend(s[i]-'a');
}
void pre() {
for (int i=1;i<=sz;i++) b[len[i]]++;
for (int i=1;i<=n;i++) b[i]+=b[i-1];
for (int i=1;i<=sz;i++) id[b[len[i]]--]=i;
for (int i=1;i<=sz;i++) mat[i]=inf;
}
void match() {
int n=strlen(s+1);
int ll=0;
for (int i=1;i<=sz;i++) f[i]=0;
for (int p=Dargen,i=1;i<=n;i++) {
while (p>1 && !ch[p][s[i]-'a']) p=par[p],ll=len[p];
if (ch[p][s[i]-'a']) {
p=ch[p][s[i]-'a'];
f[p]=max(f[p],++ll);
}
}
for (int i=sz;i>=1;i--)
if (f[id[i]]) f[par[id[i]]]=len[par[id[i]]];
for (int i=1;i<=sz;i++) mat[i]=min(mat[i],f[i]);
}
int query() {
int ans=0;
for (int i=1;i<=sz;i++) ans=max(ans,mat[i]);
return ans;
}
}
using namespace SAM; int main() {
scanf("%s",s+1);
build();
pre();
while (scanf("%s",s+1)!=EOF) match();
printf("%d",query());
return 0;
}