记录编号	251511	评测结果	AAAAAAAAAA
题目名称	[SPOJ 220] 破译进攻计划	最终得分	100
用户昵称	mikumikumi	是否通过	通过
代码语言	C++	运行时间	8.811 s
提交时间	2016-04-18 07:54:26	内存使用	9.76 MiB

#include<cstdio>
#include<cstring>
#include<iostream>
using namespace std;
const int SIZEL=11000,SIZEN=20,SIZEM=300000+10,maxn=0x7fffffff/2;
int t,N,tot;
int len[SIZEN],sa[SIZEM],rank[SIZEM],height[SIZEM];
char text[SIZEM];
void read()
{
	tot=0;
	scanf("%d",&N);
	char str[SIZEL];
	len[0]=-1;
	//int cnt=maxn;
	for(int i=1;i<=N;i++)
	{
		scanf("%s",str);
		//cnt=min(cnt,(int)strlen(str));
		for(int j=0;j<strlen(str);j++)
			text[tot++]=str[j];
		len[i]=tot;
		text[tot++]='#';
	}
	tot--;
	//cout<<cnt<<endl;
}
int sum[SIZEM];
void basesort(int a[],int b[],int c[],int n,int m)
{
	for(int i=0;i<=m;i++) sum[i]=0;
	for(int i=0;i<n;i++) sum[b[a[i]]]++;
	for(int i=1;i<=m;i++) sum[i]+=sum[i-1];
	for(int i=n-1;i>=0;i--) c[--sum[b[a[i]]]]=a[i];
}
int A[SIZEM],B[SIZEM];
int x[SIZEM],y[SIZEM];
void sortsuf(char text[],int sa[],int rank[],int n)
{
	for(int i=0;i<n;i++) A[i]=i,x[i]=text[i];
	//for(int i=0;i<n;i++) cout<<x[i]<<" ";
	//cout<<endl;
	basesort(A,x,sa,n,154);
	rank[sa[0]]=1;
	for(int i=1;i<n;i++)
	{
		if(x[sa[i]]==x[sa[i-1]]) rank[sa[i]]=rank[sa[i-1]];
		else rank[sa[i]]=rank[sa[i-1]]+1;
	}
	for(int k=1;k<=n;k<<=1)
	{
		for(int i=0;i<n;i++)
		{
			A[i]=i;
			x[i]=rank[i];
			if(i+k<n) y[i]=rank[i+k];
			else y[i]=0;
		}
		basesort(A,y,B,n,n);
		basesort(B,x,sa,n,n);
		rank[sa[0]]=1;
		for(int i=1;i<n;i++)
		{
			if(x[sa[i]]==x[sa[i-1]]&&y[sa[i]]==y[sa[i-1]]) rank[sa[i]]=rank[sa[i-1]];
			else rank[sa[i]]=rank[sa[i-1]]+1;
		}
	}
	for(int i=0;i<n;i++) rank[sa[i]]=i;
}
void make_height(int n)
{
	int h=0;
	for(int i=0;i<n;i++)
	{
		if(rank[i]==0) h=0;
		else
		{
			int k=sa[rank[i]-1];
			if(--h<0) h=0;
			while(text[i+h]==text[k+h]) h++;
		}
		height[rank[i]]=h;
	}
}
int mi[SIZEN]={0},ma[SIZEN]={0};
int ans=0;
bool check(int mid)
{
	int cnt=0;
	for(int i=0;i<=N;i++) mi[i]=maxn,ma[i]=0;
	for(int i=0;i<tot;i++)
	{
		if(height[i]>=mid)
		{
			for(int j=1;j<=N;j++)
			{
				if(sa[i]>len[j-1]&&sa[i]<len[j]) mi[j]=min(mi[j],sa[i]),ma[j]=max(ma[j],sa[i]);
				if(i>0&&sa[i-1]>len[j-1]&&sa[i-1]<len[j]) mi[j]=min(mi[j],sa[i-1]),ma[j]=max(ma[j],sa[i-1]);
			}
		}
		else
		{
			cnt=0;
			for(int j=1;j<=N;j++) if(ma[j]-mi[j]>=mid) cnt++;
			if(cnt==N) return 1;
			for(int j=1;j<=N;j++) ma[j]=-1,mi[j]=maxn;
		}
	}
	cnt=0;
	for(int j=1;j<=N;j++) if(ma[j]-mi[j]>=mid) cnt++;
	if(cnt==N) return 1;
	return 0;
}
void work()
{
	sortsuf(text,sa,rank,tot);
	make_height(tot);
	int l=0,r=tot;
	ans=0;
	while(l<r)
	{
		int mid=(l+r)/2;
		if(check(mid)) l=mid+1,ans=mid;
		else r=mid;
	}
	//while(l>0&&!check(l)) l--;
	printf("%d\n",ans);
}
int main()
{
	freopen("RelevantPhrasesofAnnihil.in","r",stdin);
	freopen("RelevantPhrasesofAnnihil.out","w",stdout);
	scanf("%d",&t);
	while(t>0)
	{
		t--;
		//cout<<"arrive"<<endl;
		read();
		//..cout<<"arive"<<" "<<tot<<endl;endl;
		//cout<<text<<endl;
		work();
	}
	return 0;
}