题目大意:
给出几个由小写字母构成的单词，求它们最长的公共子串的长度。
题解:
我们首先根据一个串构建后缀自动机
然后我们依次让每个串上去跑。
在每个节点记录一下当前已经匹配的最大的长度
然后在每次跑不同的串的过程中相应节点取min值
然后取所有的min的max输出就好了..
其实可以说成:ans是parent树中子节点的max中相应点不同串的min的max值.
...好晕啊...
#include <cstdio>
#include <cstring>
#include <algorithm>
using namespace std;
typedef long long ll;
inline void read(int &x){
x=0;char ch;bool flag = false;
while(ch=getchar(),ch<'!');if(ch == '-') ch=getchar(),flag = true;
while(x=10*x+ch-'0',ch=getchar(),ch>'!');if(flag) x=-x;
}
const int maxn = 2048;
struct Node{
int nx[26];
int len,fa;
}T[maxn<<1];
int last,nodecnt;
inline void init(){
last = nodecnt = 0;
T[0].len = 0;T[0].fa = -1;
for(int k=0;k<26;++k) T[0].nx[k] = 0;
}
inline void insert(int c){
int cur = ++ nodecnt,p;
T[cur].len = T[last].len + 1;
for(p = last;p != -1 && !T[p].nx[c];p = T[p].fa) T[p].nx[c] = cur;
if(p == -1) T[cur].fa = 0;
else{
int q = T[p].nx[c];
if(T[q].len == T[p].len + 1) T[cur].fa = q;
else{
int co = ++ nodecnt;
T[co].len = T[p].len + 1;T[co].fa = T[q].fa;
for(int i=0;i<26;++i) T[co].nx[i] = T[q].nx[i];
for(;p != -1 && T[p].nx[c] == q;p = T[p].fa) T[p].nx[c] = co;
T[cur].fa = T[q].fa = co;
}
}last = cur;
}
inline void build(char *s){
init();int len = strlen(s);
for(int i=0;i<len;++i) insert(s[i]-'a');
}
int q[maxn<<1],sum[maxn<<1];
inline void Sort(){
for(int i=1;i<=nodecnt;++i) sum[T[i].len] ++ ;
for(int i=1;i<=4000;++i) sum[i] += sum[i-1];
for(int i=1;i<=nodecnt;++i) q[sum[T[i].len]--] = i;
}
int f[maxn<<1],g[maxn<<1];
inline void find(char *s){
memset(g,0,sizeof g);
int p = 0,len = strlen(s);
for(int i=0,l = 0;i<len;++i){
int c = s[i] - 'a';
if(T[p].nx[c]) ++l,p =T[p].nx[c];
else{
while(p && !T[p].nx[c]) p = T[p].fa;
if(!p) l = 0;
else l = T[p].len+1,p = T[p].nx[c];
}g[p] = max(g[p],l);
}
for (int i=nodecnt;i;i--) g[T[q[i]].fa] = max(g[T[q[i]].fa],g[q[i]]);
for(int i=0;i<=nodecnt;++i) f[i] = min(f[i],g[i]);
}
char s[maxn<<1];
int main(){
int n;read(n);scanf("%s",s);build(s);
for(int i=1;i<=nodecnt;++i) f[i] = T[i].len;
Sort();
for(int i=2;i<=n;++i){
scanf("%s",s);
find(s);
}
int ans = 0;
for(int i=1;i<=nodecnt;++i){
ans = max(ans,f[i]);
}printf("%d
",ans);
getchar();getchar();
return 0;
}