记录编号	251185	评测结果	AAAAAAAAWA
题目名称	[SPOJ 220] 破译进攻计划	最终得分	90
用户昵称	stdafx.h	是否通过	未通过
代码语言	C++	运行时间	11.495 s
提交时间	2016-04-17 08:34:55	内存使用	6.30 MiB

#define ull unsigned int

#define maxm 12ul
#define maxn 300010ul

#include <stdio.h>
#include <string.h>
#include <algorithm>

char str[maxn];
int n,m,len,sa[maxn],pos[maxn],height[maxn],mn[maxm],mx[maxm];
ull hp[maxn],pw[maxn];
const ull base=131;

ull hashLR(int a,int b){
	if(a>b) return 0;
	return hp[b]-hp[a-1]*pw[b-a+1];
}

int lcp(int a,int b){
	int mid,l=1,r=std::min(n-a+1,n-b+1),ret=0;
	while(l<=r){
		mid=(l+r)>>1;
		if(hashLR(a,a+mid-1)==hashLR(b,b+mid-1)) l=mid+1,ret=mid;
		else r=mid-1;
	}
	return ret;
}

bool cmp(int a,int b){
	int ret=lcp(a,b),len=std::min(n-a+1,n-b+1);
	return ret==len?n-a<n-b:str[a+ret]<str[b+ret];
}

void clr(){
	memset(mn,0x2f,sizeof(mn));
	memset(mx,0,sizeof(mx));
	return;
}

bool cp(int len){
	for(int i=1;i<=m;i++) if(mx[i]-mn[i]<len)
	    return false;
	return true;
}

void upmx(int &x,int y){
	if(x<y) x=y;
	return;
}

void upmn(int &x,int y){
	if(x>y) x=y;
	return;
}

bool check(int len){
	clr();
	for(int i=1;i<=n;i++){
		if(height[sa[i]]<len){
			if(cp(len)) return true;
			clr();
		}
		upmx(mx[pos[sa[i]]],sa[i]);
		upmn(mn[pos[sa[i]]],sa[i]);
	}
	return cp(len);
}

int work(){
	int upper=0x7fffffff;
	scanf("%d",&m),memset(str,0,sizeof(str));
	for(int i=1,p=1,len,s=33;i<=m;i++){
		scanf("%s",str+p),len=strlen(str+p);
		upper=std::min(upper,len);
		for(int j=p;j<p+len;j++) pos[j]=i;
		str[p+len]=s++,p+=len+1,n=p;
	}n--;
	pw[0]=1,hp[0]=0;
	for(int i=1;i<=n;i++) pw[i]=pw[i-1]*base;
	for(int i=1;i<=n;i++) hp[i]=hp[i-1]*base+str[i];
	for(int i=1;i<=n;i++) sa[i]=i;
	std::sort(sa+1,sa+n+1,cmp);
	for(int i=1;i<=n;i++){
		if(i==1) height[sa[i]]=0;
		else height[sa[i]]=lcp(sa[i],sa[i-1]);
	}
	int ans=0,l=1,r=upper,mid;
	while(l<=r){
		mid=(l+r)>>1;
		if(check(mid)) l=mid+1,ans=mid;
		else r=mid-1;
	}
	return ans;
}

int main(){
	freopen("RelevantPhrasesofAnnihil.in","r",stdin);
	freopen("RelevantPhrasesofAnnihil.out","w",stdout);
	int T;scanf("%d",&T);
	while(T--) printf("%d\n",work());
	return 0;
}