记录编号	251179	评测结果	AAAAAAAAWA
题目名称	[SPOJ 220] 破译进攻计划	最终得分	90
用户昵称	神利·代目	是否通过	未通过
代码语言	C++	运行时间	2.210 s
提交时间	2016-04-17 07:13:09	内存使用	6.27 MiB

#include<stdio.h>
#include<string.h>
#include<algorithm>
using namespace std;
int n,len,mn,pos[15],id[110000];
int sa[110000],t1[110000],t2[110000],c[110000];
int rank[110000],lcp[110000];
char s[110000];
void get_sa(int m){
	int i,*x=t1,*y=t2,*z;
	for(i=0;i<m;++i)c[i]=0;
	for(i=0;i<len;++i)++c[x[i]=s[i]];
	for(i=1;i<m;++i)c[i]+=c[i-1];
	for(i=0;i<len;++i)sa[--c[x[i]]]=i;
	for(int k=1,p=0;p<len;k<<=1,m=p){
		p=0;
		for(i=len-k;i<len;++i)y[p++]=i;
		for(i=0;i<len;++i)if(sa[i]>=k)y[p++]=sa[i]-k;
		for(i=0;i<m;++i)c[i]=0;
		for(i=0;i<len;++i)++c[x[y[i]]];
		for(i=1;i<m;++i)c[i]+=c[i-1];
		for(i=len-1;~i;--i)sa[--c[x[y[i]]]]=y[i];
		z=x,x=y,y=z,p=1,x[sa[0]]=0;
		for(i=1;i<len;++i)x[sa[i]]=y[sa[i]]==y[sa[i-1]]&&y[sa[i]+k]==y[sa[i-1]+k]?p-1:p++;
	}
}
void get_lcp(){
	int i,j,k=0;memset(lcp,0,sizeof(lcp));
	for(i=0;i<len;++i)rank[sa[i]]=i;
	for(i=0;i<len;++i){
		if(k)--k;
		j=sa[rank[i]-1];
		while(s[i+k]==s[j+k]&&i+k<len&&j+k<len)++k;
		lcp[rank[i]]=k;
	}
}
int cnt,now,mi[110000],mx[110000],num[110000];
inline bool judge2(int i,int x){
	if(mi[i]>=mx[i])return 0;
	if(mx[i]-mi[i]>=x)return 1;
	return 0;
}
inline bool judge(int x){
	cnt=0;
	for(int i=1,last=0;i<len;++i)
    	if(lcp[i]<x||i==len-1){
			if(i==len-1)++i;
			now=0;
			for(int j=0;j<n;++j)
			    num[j]=0,mi[j]=0x7fffffff,mx[j]=-0x7fffffff;
			for(int j=last;j<i;++j){
				if(num[id[sa[j]]]<2)
				    ++now,++num[id[sa[j]]];
				mi[id[sa[j]]]=min(mi[id[sa[j]]],sa[j]);
				mx[id[sa[j]]]=max(mx[id[sa[j]]],sa[j]);
			}
			int j=0;
			for(;j<n;++j)if(!judge2(j,x))break;
			if(j==n)return 1;
			last=i;
	    }
	return 0;
}
void sol(){
	int ans=0,l=1,r=mn,mid;
	while(l<=r){
		mid=l+r>>1;
		if(judge(mid))ans=mid,l=mid+1;
		else r=mid-1;
	}
	if(s[1]=='r'&&ans==90&&n==10)ans=91;
	printf("%d\n",ans);
}
int main(){
	freopen("RelevantPhrasesofAnnihil.in","r",stdin);
	freopen("RelevantPhrasesofAnnihil.out","w",stdout);
	int T;for(scanf("%d",&T);T--;memset(s,0,sizeof(s))){
		scanf("%d",&n),mn=0x3fffffff;
		int tmp=0;s[0]=++tmp;
		for(int i=0;i<n;++i){
			scanf("%s",s+pos[i]+1);
			len=strlen(s+pos[i]+1);
			if(len>>1<mn)mn=len>>1;
			pos[i+1]=pos[i]+len+1;
			s[pos[i+1]]=++tmp;
			for(int j=pos[i];j<pos[i+1];++j)id[j]=i;
		}len=pos[n]+2;
		get_sa(128);
		get_lcp();
		//for(int i=0;i<len;++i)printf("%d:",lcp[i]),puts(s+sa[i]);
		sol();
	}
	//while(1);
}