记录编号	218929	评测结果	AAAAAAAAAA
题目名称	[SPOJ 687] 重复的字符串	最终得分	100
用户昵称	mikumikumi	是否通过	通过
代码语言	C++	运行时间	8.659 s
提交时间	2016-01-12 11:07:06	内存使用	7.01 MiB

#include<cstdio>
#include<cstring>
#include<iostream>
#include<cmath>
using namespace std;
const int SIZEN=60010,SIZEG=20;
int T,N;
char p[SIZEN];
int t[SIZEN]={0},rank[SIZEN],sa[SIZEN],height[SIZEN];
int A[SIZEN],B[SIZEN];
int x[SIZEN],y[SIZEN];
int sum[SIZEN];
int ST[SIZEN][SIZEG];
void basesort(int a[],int b[],int c[],int n,int m)
{
	for(int i=0;i<=m;i++) sum[i]=0;
	for(int i=0;i<n;i++) sum[b[a[i]]]++;
	for(int i=1;i<=m;i++) sum[i]+=sum[i-1];
	for(int i=n-1;i>=0;i--) c[--sum[b[a[i]]]]=a[i];
}
void sort_suf(int t[],int rank[],int sa[],int n)
{
	for(int i=0;i<n;i++) A[i]=i,x[i]=t[i];
	basesort(A,x,sa,n,2);
	rank[sa[0]]=1;
	for(int i=1;i<n;i++) if(x[sa[i]]==x[sa[i-1]]) rank[sa[i]]=rank[sa[i-1]];
	else rank[sa[i]]=rank[sa[i-1]]+1;
	for(int k=1;k<=n;k<<=1)
	{
		for(int i=0;i<n;i++)
		{
			A[i]=i;
			x[i]=rank[i];
			if(i+k<n) y[i]=rank[i+k];
			else y[i]=0;
		}
		basesort(A,y,B,n,n);
		basesort(B,x,sa,n,n);
		//for(int i=0;i<n;i++) cout<<i<<" "<<sa[i]<<endl;
		//cout<<endl;
		rank[sa[0]]=1;
		for(int i=1;i<n;i++)
			if(x[sa[i]]==x[sa[i-1]]&&y[sa[i]]==y[sa[i-1]]) rank[sa[i]]=rank[sa[i-1]];
		else rank[sa[i]]=rank[sa[i-1]]+1;
		//for(int i=0;i<n;i++) cout<<i<<" "<<rank[i]<<endl;
		//cout<<endl;
	}
}
void make_height()
{
	int h=0;
	for(int i=0;i<N;i++)
	{
		if(rank[i]==1) h=0;
		else
		{
			int k=sa[rank[i]-2];
			if(--h<0) h=0;
			while(t[i+h]==t[k+h]) h++;
		}
		height[rank[i]]=h;
	}
}
void make_ST()
{
	int n=int(log2(N+1.0));
	for(int i=0;i<=N;i++) ST[i][0]=height[i];
	for(int j=1;j<=n;j++)
	{
		
		for(int i=0;i<=N;i++)
		{
			//cout<<i<<endl;//" "<<" "<<i+(1<<(j-1))<<" "<<j<<endl;
			ST[i][j]=min(ST[i][j-1],ST[i+(1<<(j-1))][j-1]);
		}
	}
}
void read()
{
	scanf("%d",&N);
	memset(t,0,sizeof(t));
	memset(ST,0,sizeof(ST));
	memset(height,0,sizeof(height));
	for(int i=0;i<N;i++)
	{
		cin>>p[i];
		if(p[i]=='a') t[i]=1;
		else t[i]=2;
	}
}
int RMQ(int x,int y)
{
	int p=int(log2(y-x+1));
	int re=min(ST[x][p],ST[y-(1<<p)+1][p]);
	return re;
}
int lcp(int x,int y)
{
	if(x==y) return N-x;
	int a=rank[x],b=rank[y];
	if(a>b) swap(a,b);
	return RMQ(a+1,b);
}
int ans;
void test(int x)
{
	for(int i=0;i<N;i+=x)
	{
		int tem=lcp(i,i+x);
		int st=i-(x-tem%x);
		int pos=tem/x+1;
		if(st>0&&tem%x!=0)
		{
			if(lcp(st,st+x)>tem) pos++;
		}
		ans=max(ans,pos);
	}
}
void work()
{
	ans=0;
	for(int i=1;i<=N;i++) test(i);
	printf("%d\n",ans);
}
void prepare()
{
	sort_suf(t,rank,sa,N);
	make_height();
	make_ST();
}
int main()
{
	freopen("repeats.in","r",stdin);
	freopen("repeats.out","w",stdout);
	scanf("%d",&T);
	int now=1;
	while(now<=T)
	{
		read();
		prepare();
		work();
		now++;
	}
	return 0;
}