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

#define MAXN 50010UL
#define MAXC 5UL
#define BASE 11LL

#define ll long long

#include <cstdio>
#include <cstring>
#include <algorithm>

int n,sa[MAXN],p[MAXN],f[MAXN],height[MAXN],Ans;
char op[MAXC],s[MAXN];
ll hash[MAXN],power[MAXN];
const ll PRIME=(ll)((1e9)+7);

inline int MIN(int a,int b){
	return a<b?a:b;
}

inline ll Hash(int l,int r){
	return ((hash[r]-hash[l-1]*power[r-l+1])%PRIME+PRIME)%PRIME;
}

inline bool Check(int a,int b,int len){
	return Hash(a,a+len-1)==Hash(b,b+len-1);
}

inline int LCP(int a,int b){
	int temp_ans=0,L=0,R=MIN(n-a,n-b)+1,mid;
	while(L<=R){
		mid=(L+R)>>1;
		if(Check(a,b,mid)) temp_ans=mid,L=mid+1;
		else R=mid-1;
	}
	return temp_ans;
}

inline bool comp(int a,int b){
	int len=LCP(a,b);
	return s[a+len]<s[b+len];
}

inline void DP(int len){
	p[sa[1]]=0;
	for(int i=2,cnt=0;i<=n;i++){
		if(height[i]<len) cnt++;
		p[sa[i]]=cnt;
	}
	for(int i=1;i<=len;i++) f[i]=1;
	for(int i=len+1;i<=n;i++){
		if(p[i]==p[i-len]) f[i]=f[i-len]+1;
		else f[i]=1;
		if(f[i]>Ans) Ans=f[i];
	}
	return;
}

inline void Work(){
	Ans=1;
	memset(s,0,sizeof(s));
	scanf("%d",&n);
	for(int i=1;i<=n;i++)
		scanf("%s",op),s[i]=op[0],hash[i]=(hash[i-1]*BASE+op[0])%PRIME,sa[i]=i;
	std::sort(sa+1,sa+n+1,comp);
	for(int i=2;i<=n;i++)
		height[i]=LCP(sa[i-1],sa[i]);
	for(int i=1;i<=n;i++){
		if(n/i<=Ans) break;
		DP(i);
	}
	printf("%d\n",Ans);
	return;
}

int main(){
	freopen("repeats.in","r",stdin);
	freopen("repeats.out","w",stdout);
	int t;
	scanf("%d",&t);
	power[0]=1;
	for(int i=1;i<MAXN;i++)
		power[i]=(power[i-1]*BASE)%PRIME;
	for(int i=1;i<=t;i++)
		Work();
	return 0;
}