记录编号	379636	评测结果	AAAAAAAAAAAAAAAAAAAA
题目名称	[POI 2000] 最长公共子串	最终得分	100
用户昵称	AntiLeaf	是否通过	通过
代码语言	C++	运行时间	0.048 s
提交时间	2017-03-07 07:22:41	内存使用	24.51 MiB

#include<cstdio>
#include<cstring>
#include<algorithm>
using namespace std;
const int maxn=200010;
void expand(int);
void match(const char*);
int root,last,cnt=0,val[maxn]={0},par[maxn]={0},go[maxn][26]={{0}},a[maxn],b[maxn];
char s[maxn];
int T,n,c[maxn>>1]={0},d[maxn],tim=0,ans=0;
int main(){
	freopen("pow.in","r",stdin);
	freopen("pow.out","w",stdout);
	memset(b,63,sizeof(b));
	root=last=++cnt;
	scanf("%d%s",&T,s);
	n=strlen(s);
	for(int i=0;i<n;i++)expand(s[i]-'a');
	for(int i=1;i<=cnt;i++)c[val[i]+1]++;
	for(int i=1;i<=n;i++)c[i]+=c[i-1];
	for(int i=1;i<=cnt;i++)d[++c[val[i]]]=i;
	while(--T){
		scanf("%s",s);
		match(s);
	}
	for(int i=1;i<=cnt;i++)ans=max(ans,b[i]);
	printf("%d\n",ans);
	return 0;
}
void expand(int c){
	int p=last,np=++cnt;
	val[np]=val[p]+1;
	while(p&&!go[p][c]){
		go[p][c]=np;
		p=par[p];
	}
	if(!p)par[np]=root;
	else{
		int q=go[p][c];
		if(val[q]==val[p]+1)par[np]=q;
		else{
			int nq=++cnt;
			val[nq]=val[p]+1;
			memcpy(go[nq],go[q],sizeof(go[q]));
			par[nq]=par[q];
			par[np]=par[q]=nq;
			while(p&&go[p][c]==q){
				go[p][c]=nq;
				p=par[p];
			}
		}
	}
	last=np;
}
void match(const char *c){
	fill(a,a+cnt+1,0);
	for(int x=root,len=0;*c;c++){
		while(x&&!go[x][*c-'a']){
			x=par[x];
			len=val[x];
		}
		if(!x){
			x=root;
			len=0;
		}
		else{
			x=go[x][*c-'a'];
			len++;
		}
		a[x]=max(a[x],len);
	}
	for(int i=1;i<=cnt;i++)b[i]=min(b[i],a[i]);
	for(int i=cnt;i;i--)b[par[d[i]]]=max(b[par[d[i]]],b[d[i]]);
}