记录编号	215518	评测结果	AAAAAAAAAA
题目名称	[SPOJ 687] 重复的字符串	最终得分	100
用户昵称	zys	是否通过	通过
代码语言	C++	运行时间	30.707 s
提交时间	2015-12-22 11:44:45	内存使用	5.49 MiB

#define Max(a,b)((a)>(b)?(a):(b))
#define Min(a,b)((a)<(b)?(a):(b))

#include<cstdio>
#include<cstring>

using namespace std;

char s[50010],c[100];
int rmq[50010][20],ws[50010],wv[50010],L,R,tmp,wb[50010];
int q,n,m,wa[50010],rank[50010],sa[50010],h[50010],Mid,Ans,tMin,tMax;

bool cmp(int *r,int a,int b,int l)
{
	return r[a]==r[b]&&r[a+l]==r[b+l];
}

void Get_sa()
{
	int i,j,p=0,*x=wa,*y=wb,*t;
	for(i=0;i<=m;i++)ws[i]=0;
	for(i=1;i<=n;i++)ws[x[i]=s[i]]++;
	for(i=1;i<=m;i++)ws[i]+=ws[i-1];
	for(i=n;i>=1;i--)sa[ws[x[i]]--]=i;
	for(j=1;p<n;j<<=1,m=p){
		for(p=0,i=n-j+1;i<=n;i++)y[++p]=i;
		for(i=1;i<=n;i++)if(sa[i]>j)y[++p]=sa[i]-j;
		for(i=0;i<=m;i++)ws[i]=0;
		for(i=1;i<=n;i++)wv[i]=x[y[i]];
		for(i=1;i<=n;i++)ws[wv[i]]++;
		for(i=1;i<=m;i++)ws[i]+=ws[i-1];
		for(i=n;i>=1;i--)sa[ws[wv[i]]--]=y[i];
		for(t=x,x=y,y=t,x[sa[1]]=1,p=1,i=2;i<=n;i++)
		    x[sa[i]]=cmp(y,sa[i],sa[i-1],j)?p:(++p);
	}
}

void Get_height()
{
	int i,j,k=0;
	for(i=1;i<=n;i++)rank[sa[i]]=i;
	for(i=1;i<=n;h[rank[i++]]=k)
	for(k?k--:k=0,j=sa[rank[i]-1];s[i+k]==s[j+k];k++);
}

int Query(int l,int r)
{
	int k=0;L=r-l+1;while((1<<k)<=L)k++;k--;
	return Min(rmq[l][k],rmq[r-(1<<k)+1][k]);
}

int main()
{
	freopen("repeats.in","r",stdin);
	freopen("repeats.out","w",stdout);
	scanf("%d",&q);
	while(q--){
		scanf("%d",&n);Ans=1;memset(rmq,0,sizeof(rmq));
		memset(h,0,sizeof(h));memset(sa,0,sizeof(sa));
		memset(wa,0,sizeof(wa));memset(wb,0,sizeof(wb));
		memset(rank,0,sizeof(rank));memset(s,0,sizeof(s));
		memset(c,0,sizeof(c));memset(wv,0,sizeof(wv));
		for(int i=1;i<=n;i++){scanf("%s",c);s[i]=c[0];}
		m='b';Get_sa();Get_height();
		for(int i=1;i<=n;i++)rmq[i][0]=h[i];
		for(int k=1,l=1;l<=n;k++,l<<=1)for(int i=1;i<=n-l+1;i++)
		    rmq[i][k]=Min(rmq[i][k-1],rmq[i+l][k-1]);
		for(int l=1;l<=n;l++){
			for(int k=0;(k+1)*l+1<=n;k++){
				L=1;R=k*l+1;tmp=0;
				while(L<=R){
					Mid=(L+R)>>1;
					tMin=Min(rank[Mid],rank[Mid+l]);
					tMax=Max(rank[Mid],rank[Mid+l]);
					if(Query(tMin+1,tMax)>tmp)
						R=Mid-1,tmp=Query(tMin+1,tMax);
					else L=Mid+1;
				}
				tmp=tmp/l+1;
				if(tmp>Ans)Ans=tmp;
			}
		}
		printf("%d\n",Ans);
	}
}