记录编号	378829	评测结果	AAAAAAAAAA
题目名称	[HZOI 2016] 寒假ing	最终得分	100
用户昵称	rewine	是否通过	通过
代码语言	C++	运行时间	2.211 s
提交时间	2017-03-05 08:27:24	内存使用	43.91 MiB

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

void read(int &x) {
	char c;bool flag(0);
	while((c=getchar())<'0'||c>'9') flag |= c=='-';
	x=c-'0';while((c=getchar())>='0'&&c<='9') x=(x<<1)+(x<<3)+c-'0';
	flag ? x=-x:x;
}

using namespace std;

#define N 401000

#define All for(int i = 0; i < n; i++)

void radix(int *s,int *a,int *b,int n,int m) {
    static int c[N];
    for (int i = 0; i <= m; i++) c[i] = 0;
    for (int i = 0; i < n; i++) ++c[s[a[i]]];
    for (int i = 1; i <= m; i++) c[i] += c[i-1];
	for (int i = n-1; i >= 0; i--) b[--c[s[a[i]]]] = a[i];
}

void suffix(int *s,int *sa,int n,int m) {
    static int rk[N],a[N],b[N];
	for (int i = 0; i < n; i++) rk[i] = i;
	radix(s,rk,sa,n,m); rk[sa[0]] = 0;
	for (int i = 1; i < n; i++)
	 rk[sa[i]] = rk[sa[i-1]]+(s[sa[i-1]]==s[sa[i]]?0:1);
	for (int i = 0; 1<<i < n; i++) {
		for (int j = 0; j < n; j++) {
			a[j] = rk[j]+1;	sa[j] = j;
			b[j] = j+(1<<i)>=n?0:rk[j+(1<<i)]+1;
		}
		radix(b,sa,rk,n,n); radix(a,rk,sa,n,n);
		rk[sa[0]] = 0;
		for (int j = 1; j < n; j++)
		 rk[sa[j]] = rk[sa[j-1]]+(a[sa[j-1]]==a[sa[j]]&&b[sa[j-1]]==b[sa[j]]?0:1);
	}
}

void calc_ht(int *s,int *sa,int *ht,int *rk,int n) {
    int k = 0,j;  ht[0] = 0;
	for (int i = 0; i < n; i++) rk[sa[i]] = i;
	for (int i = 0; i < n; i++) {
	   k?--k:0; j = sa[rk[i]-1];
	   if(!rk[i]) k = 0;
	   else while(s[i+k] == s[j+k]) k++;
       ht[rk[i]] = k;
	}
}


char s1[N],s2[N];
int sa[N],rk[N],h[N],a[N],n,f[N][20];

void st_init() {
	for (int i = 0; i < n; i++) f[i][0] = h[i];
	for (int i = 1; 1<<i < n; i++)
	 for (int j = 0; j+(1<<i)-1 < n; j++)
	  f[j][i] = min(f[j][i-1],f[j+(1<<i-1)][i-1]);
}

int Lcp(int l,int r) {
	l = rk[l]; r = rk[r];
	if(l > r) swap(l,r); l++;
	int k = 0;
	while(1<<k+1 <= r-l+1) k++;
	return min(f[l][k],f[r-(1<<k)+1][k]);
}

int calc(int L) {
	int tmp = 1,ans = 1;
	for (int i = 0; i+L < n; i += L) {
		int R = Lcp(i,i+L);
		ans = max(ans,R/L+1);
		if(i-L+R%L >= 0)
	 	  ans = max(ans,Lcp(i-L+R%L,i+R%L)/L+1);
	}
	return ans;
}

int main() {
    freopen("broken.in","r",stdin); freopen("broken.out","w",stdout);
    int _;
    for(read(_); _; --_) {
	    read(n); scanf("%s",s1);
	    copy(s1,s1+n,a);
	    suffix(a,sa,n,256);
	    calc_ht(a,sa,h,rk,n);
	    st_init();
	    int ans = 0;
	    for (int i = 1; i <= n; i++) ans = max(ans,calc(i));
	    printf("%d\n",ans);
	}
	return 0;
}