#include <iostream>
#include <cstdio>
#include <cmath>
#include <algorithm>
#include <cstring>
#define maxn 4005
#define maxm 2005
using namespace std; int n,m,tot,last,root,len,smin[maxn],sum[maxn],tmp[maxn],fa[maxn],son[maxn][],dist[maxn];
char st[maxm];
struct Tsegment{
int ans[maxn];
void prepare(){tot=last=root=;}
int newnode(int x){dist[++tot]=x;return tot;}
void add(int x){
int p=last,np=newnode(dist[p]+); last=np;
for (;p&&!son[p][x];p=fa[p]) son[p][x]=np;
if (p==) fa[np]=root;
else{
int q=son[p][x];
if (dist[p]+==dist[q]) fa[np]=q;
else{
int nq=newnode(dist[p]+);
memcpy(son[nq],son[q],sizeof(son[q]));
fa[nq]=fa[q],fa[q]=fa[np]=nq;
for (;p&&son[p][x]==q;p=fa[p]) son[p][x]=nq;
}
}
}
void Fsort(){
memset(sum,,sizeof(sum));
for (int i=;i<=tot;i++) ans[i]=dist[i];
for (int i=;i<=tot;i++) sum[dist[i]]++;
for (int i=;i<=tot;i++) sum[i]+=sum[i-];
for (int i=;i<=tot;i++) tmp[sum[dist[i]]--]=i;
}
void work(){
scanf("%s",st+),m=strlen(st+);int x;
memset(smin,,sizeof(smin)),len=,last=root;
for (int i=;i<=m;i++){
x=st[i]-'a';
if (son[last][x]) len++,last=son[last][x];
else{
for (;last&&!son[last][x];) last=fa[last];
if (last==) len=,last=root;
else{
len=dist[last]+,last=son[last][x];
}
}
smin[last]=max(smin[last],len);
}
for (int i=tot;i>=;i--){
x=tmp[i];
ans[x]=min(ans[x],smin[x]);
if (fa[x]&&smin[x]) smin[fa[x]]=dist[fa[x]];
}
}
}SAM; int main(){
int ans=;
scanf("%d",&n),n--;
SAM.prepare();
scanf("%s",st+),m=strlen(st+);
for (int i=;i<=m;i++) SAM.add(st[i]-'a');
SAM.Fsort();
for (int i=;i<=n;i++) SAM.work();
for (int i=;i<=tot;i++) ans=max(ans,SAM.ans[i]);
printf("%d\n",ans);
return ;
}

题目链接:http://www.lydsy.com/JudgeOnline/problem.php?id=2946

http://begin.lydsy.com/JudgeOnline/problem.php?id=2797

题目大意:给定n个字符串,n不大于5,每个字符串的长度不大于2000,求这n个字符串的最长公共子串的长度。

做法:首先,这题还是可以用后缀数组+二分答案解决,那后缀自动机怎么解决呢?

首先对其中一个串建立后缀自动机,其他串在上面匹配即可,失配则跳parent树。

对于多串,我们在每个节点上记录一个信息,表示所有匹配的字符串匹配到该节点是最小的长度,每次用该字符串在SAM上每个点的最大匹配长度去更新要维护的信息(最小的长度),原因自己YY一下即可,木桶效应嘛。

特别注意:在后缀自动机上匹配到一个节点时,那么它的所有祖先(通过fa一路可以到达的节点)都能匹配到其最大长度,每次记得通过一次dp得到。

后缀自动机。

05-11 15:51