本文版权归ljh2000和博客园共有，欢迎转载，但须保留此声明，并给出原文链接，谢谢合作。
本文作者：ljh2000
作者博客：http://www.cnblogs.com/ljh2000-jump/
转载请注明出处，侵权必究，保留最终解释权！
题目链接：SPOJ1812
正解：后缀自动机
解题报告：
和上一道题差不多，只不过变成了多串匹配。
这样的话就不能直接更新答案了，那我们考虑怎么做呢…
我们每次更新答案的时候是在一个匹配上的结点上更新，而多个串我们容易发现对于同一个结点上的匹配我们只要取一个$min$就可以得到多个串在这个位置的匹配了。
最后对所有节点上的$ans$取个$max$即可。
//It is made by ljh2000
//有志者，事竟成，破釜沉舟，百二秦关终属楚；苦心人，天不负，卧薪尝胆，三千越甲可吞吴。
#include <iostream>
#include <cstdlib>
#include <cstring>
#include <cstdio>
#include <cmath>
#include <algorithm>
#include <ctime>
#include <vector>
#include <queue>
#include <map>
#include <set>
#include <string>
#include <complex>
#include <bitset>
using namespace std;
typedef long long LL;
typedef long double LB;
typedef complex<double> C;
const double pi = acos(-1);
const int MAXN = 200011;
int n,m,cnt,S,last,ch[MAXN][26],a[MAXN],len[MAXN],fa[MAXN],L;
int f[MAXN],g[MAXN],ans,tong[MAXN],sa[MAXN];
char s[MAXN];
inline int getint(){
int w=0,q=0; char c=getchar(); while((c<'0'||c>'9') && c!='-') c=getchar();
if(c=='-') q=1,c=getchar(); while (c>='0'&&c<='9') w=w*10+c-'0',c=getchar(); return q?-w:w;
}
inline void add(int x){
int c=a[x],p=last,np=++cnt; last=cnt;
len[np]=x; for(;p && !ch[p][c];p=fa[p]) ch[p][c]=np;
if(!p) fa[np]=S;
else {
int q=ch[p][c];
if(len[q]==len[p]+1) fa[np]=q;
else {
int nq=++cnt; len[nq]=len[p]+1;
memcpy(ch[nq],ch[q],sizeof(ch[q]));
fa[nq]=fa[q];//!!!
fa[np]=fa[q]=nq;
for(;ch[p][c]==q;p=fa[p]) ch[p][c]=nq;
}
}
}
inline void build(){
scanf("%s",s+1); n=strlen(s+1); S=last=++cnt;
for(int i=1;i<=n;i++) a[i]=s[i]-'a';
for(int i=1;i<=n;i++) add(i);
for(int i=1;i<=cnt;i++) g[i]=(1<<30);
for(int i=1;i<=cnt;i++) tong[ len[i] ]++;
for(int i=1;i<=n;i++) tong[i]+=tong[i-1];
for(int i=1;i<=cnt;i++) sa[ tong[ len[i] ] -- ]=i;
}
inline void solve(){
m=strlen(s+1); int L=0,p=S,now;
for(int i=1;i<=cnt;i++) f[i]=0;
for(int i=1;i<=m;i++) {
now=s[i]-'a';
while(p>S && !ch[p][now]) p=fa[p],L=len[p];
if(ch[p][now]) {
p=ch[p][now];//!!!
L++;
f[p]=max(L,f[p]);
}
}
for(int i=cnt;i>=1;i--)
if(f[sa[i]]) f[ fa[ sa[i] ] ]=len[ fa[ sa[i] ] ];//逆序更新一遍!把儿子的信息传到父亲节点上去!父亲的状态是一个后缀，显然也能更新!
for(int i=1;i<=cnt;i++) g[i]=min(g[i],f[i]);
}
inline void work(){
build();
while(scanf("%s",s+1)!=EOF)
solve();
for(int i=1;i<=cnt;i++) ans=max(ans,g[i]);
printf("%d",ans);
}
int main()
{
work();
return 0;
}
//有志者，事竟成，破釜沉舟，百二秦关终属楚；苦心人，天不负，卧薪尝胆，三千越甲可吞吴。