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

#include <cstdio>
#include <algorithm>
#include <cstring>
#include <ctime>
using namespace std;
const int maxn = 50010;
char ch[maxn]="\0";
int wa[maxn],wb[maxn],sa[maxn],bucket[maxn],Rank[maxn];
int height[maxn],st[20][maxn] = {0},Log2[maxn];
int N,M;
bool Cmp(const int *r,int x,int y,int k)
{return r[x]==r[y]&&r[x+k]==r[y+k];}
void doubling(const int *r,int n,int m){
	int *t,*x=wa,*y=wb,i,j,p;
	for(i = 0;i <= m;i++)bucket[i] = 0;
	for(i = 0;i < n;i++)bucket[x[i]=r[i]]++;
	for(i = 1;i <=m;i++)bucket[i]+=bucket[i-1];
	for(i = n-1;i>=0;i--)sa[--bucket[x[i]]] = i;
	for(j=1,p=1;p<n;m=p,j<<=1){
		for(i = n-j,p=0;i<n;i++)y[p++]=i;
		for(i = 0;i < n;i++)if(sa[i] >= j)y[p++] = sa[i]-j;
		for(i = 0;i <= m;i++)bucket[i] = 0;
		for(i = 0;i < n;i++)bucket[x[y[i]]]++;
		for(i = 1;i <= m;i++)bucket[i] += bucket[i-1];
		for(i=n-1;i>=0;i--)sa[--bucket[x[y[i]]]] = y[i];
		for(t=x,x=y,y=t,i=1,p=1,x[sa[0]]=0;i<n;i++)
			x[sa[i]]=Cmp(y,sa[i],sa[i-1],j)?p-1:p++;
	}
}
void Calheight(const int *r,int n){
	int i,j,k=0;
	for(i = 1;i <=n;i++)Rank[sa[i]] = i;
	for(i = 0;i < n;height[Rank[i++]]=k)
		for(k?k--:0,j=sa[Rank[i]-1];r[i+k]==r[j+k];k++);
}
void RMQ_Init(int n){
	memset(st,0x3f,sizeof st);
	for(int i = 0;i <= n;i++)st[0][i]=height[i+1];
	for(int i = 1;i <= Log2[n];i++)
		for(int j = 0;j <= n;j++){
			st[i][j]=st[i-1][j];
			if(j+(1<<i-1) <= n)st[i][j] = min(st[i][j],st[i-1][j+(1<<i-1)]);
		}
}
int LCP_ask(int l,int r){
	if(l > r)swap(l,r);r --;
	int k = Log2[r-l+1],q = min(st[k][l],st[k][r-(1<<k)+1]);
	if(q >= 0x3f3f3f3f)return -4654564;
	return min(st[k][l],st[k][r-(1<<k)+1]);
}
int r[maxn];
int main(){
	freopen("broken.in","r",stdin);
	freopen("broken.out","w",stdout);
	Log2[1] = 0;
	for(int i = 2;i <= maxn-10;i++){
		Log2[i] = Log2[i-1];
		if((1<<Log2[i]+1) == i)Log2[i]++;
	}
	int T;scanf("%d",&T);
	while(T--){
		int len = 0;                                                              
		scanf("%d",&len);
		memset(r,0,sizeof(r));
		scanf("%s",ch);r[len]=0;
		for(int i = 0;i < len;i++)r[i]=ch[i];
		doubling(r,len+1,200);
		Calheight(r,len);
		RMQ_Init(len);
		int k,jj,now,l,ans = 0;
		for(l=1;l < len;l++){
			for(int i = 0;i+l < len;i+=l){
				k = LCP_ask(Rank[i],Rank[i+l]);
				now = k/l;
				jj = l-k%l;jj = i-jj;
				if(k%l&&jj >= 0)now = max(now,LCP_ask(Rank[jj],Rank[jj+l])/l);
				if(now)ans = max(ans,now);
			}
		}
		printf("%d\n",ans+1);
	}
}