记录编号	366898	评测结果	AAAAAAAAAA
题目名称	[HZOI 2016] 寒假ing	最终得分	100
用户昵称	FoolMike	是否通过	通过
代码语言	C++	运行时间	1.924 s
提交时间	2017-01-26 14:56:29	内存使用	21.85 MiB

#include<cstdio>
#include<algorithm>
#include<cstring>
using namespace std;
const int N=2e5+10;
char s[N];
int n,sa[N],r[N],h[N],Wa[N],Wb[N],Wv[N],Ws[N],t[20],lg[N];
bool cmp(int *r,int x,int y,int l){
	return r[x]==r[y]&&r[x+l]==r[y+l];
}
void da(){
	int i,m=100,*x=Wa,*y=Wb;
	memset(Wa,0,sizeof Wa);
	memset(Wb,0,sizeof Wb);
	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;i--) sa[Ws[x[i]]--]=i;
	for (int l=1,p=0;p<n;m=p,l<<=1){
		for (i=n-l+1,p=0;i<=n;i++) y[++p]=i;
		for (i=1;i<=n;i++)
			if (sa[i]>l) y[++p]=sa[i]-l;
		for (i=0;i<=m;i++) Ws[i]=0;
		for (i=1;i<=n;i++) Ws[x[y[i]]]++;
		for (i=1;i<=m;i++) Ws[i]+=Ws[i-1];
		for (i=n;i;i--) sa[Ws[x[y[i]]]--]=y[i];
		swap(x,y);
		for (p=x[sa[1]]=1,i=2;i<=n;i++)
			x[sa[i]]=cmp(y,sa[i],sa[i-1],l)?p:++p;
	}
}
int dp[N][20];
void geth(){
	int i,j,k;
	for (i=1;i<=n;i++) r[sa[i]]=i;
	for (k=h[r[0]]=0,i=1;i<=n;h[r[i++]]=k)
	for (k=max(h[r[i-1]]-1,0),j=sa[r[i]-1];s[i+k]==s[j+k];k++);
	for (i=1;i<=n;i++) dp[i][0]=h[i];
	for (j=1;j<=lg[n];j++)
		for (i=1;i+t[j]-1<=n;i++)
			dp[i][j]=min(dp[i][j-1],dp[i+t[j-1]][j-1]);
}
int lcp(int x,int y){
	x=r[x];y=r[y];
	if (x>y) swap(x,y);
	int k=lg[y-x];
	return min(dp[x+1][k],dp[y-t[k]+1][k]);
}
int main()
{
	t[0]=1;
	for (int i=1;i<18;i++){
		t[i]=1<<i;
		for (int j=t[i-1];j<t[i];j++) lg[j]=i-1;
	}
	freopen("broken.in","r",stdin);
	freopen("broken.out","w",stdout);
	int T;scanf("%d",&T);
	while (T--){
		scanf("%d%s",&n,s+1);
		for (int i=1;i<=n;i++) s[i]-='a'-1;
		da();geth();
		int ans=1;
		for (int L=1;L<=n;L++)
		for (int i=L+L;i<=n;i+=L){
			int x=i-L,y=i,len=lcp(x,y);
			if (len%L){
				int pre=L-len%L;
				len=max(len,lcp(x-pre,y-pre));
			} 
			ans=max(ans,len/L+1);
		}
		printf("%d\n",ans);
	}
	return 0;
}