记录编号	370043	评测结果	AAAAATTTTT
题目名称	[HZOI 2016] 寒假ing	最终得分	50
用户昵称	AntiLeaf	是否通过	未通过
代码语言	C++	运行时间	5.309 s
提交时间	2017-02-12 18:04:07	内存使用	57.97 MiB

#include<cstdio>
#include<cstring>
#include<algorithm>
#include<map>
#include<vector>
using namespace std;
const int maxn=50010;
struct Suffix_Automaton{
	int root,last,cnt,val[maxn<<1],par[maxn<<1],go[maxn<<1][26],iter[maxn];
	vector<int>G[maxn<<1];
	int dfn[maxn<<1],d[maxn<<1],tim,f[maxn<<2][20],log_tbl[maxn<<2];//用于求LCA
	Suffix_Automaton(){
		log_tbl[0]=-1;//预处理对数使得ST的查询是严格O(1)
		for(int i=1;i<maxn<<2;i++)log_tbl[i]=log_tbl[i>>1]+1;
	}
	void clear(){
		root=last=cnt=1;
		tim=0;
		memset(go,0,sizeof(go));
		memset(val,0,sizeof(val));
		memset(par,0,sizeof(par));
		memset(iter,0,sizeof(iter));
		memset(dfn,0,sizeof(dfn));
		memset(d,0,sizeof(d));
		memset(f,0,sizeof(f));
		for(int i=0;i<maxn<<1;i++)G[i].clear();
	}
	void expand(int c,int x){
		int p=last,np=++cnt;
		val[np]=val[p]+1;
		while(p&&!go[p][c]){
			go[p][c]=np;
			p=par[p];
		}
		if(!p)par[np]=root;
		else{
			int q=go[p][c];
			if(val[q]==val[p]+1)par[np]=q;
			else{
				int nq=++cnt;
				memcpy(go[nq],go[q],sizeof(go[q]));
				val[nq]=val[p]+1;
				par[nq]=par[q];
				par[np]=par[q]=nq;
				while(p&&go[p][c]==q){
					go[p][c]=nq;
					p=par[p];
				}
			}
		}
		iter[x]=last=np;
	}
	void LCP_init(){//预处理LCA
		for(int i=2;i<=cnt;i++)G[par[i]].push_back(i);
		dfs(root);
		d[0]=10000000;
		for(int j=1;(1<<j)<=tim;j++)for(int i=1;i+(1<<j)-1<=tim;i++)
			f[i][j]=d[f[i][j-1]]<d[f[i+(1<<(j-1))][j-1]]?f[i][j-1]:f[i+(1<<(j-1))][j-1];
	}
	void dfs(int x){
		f[dfn[x]=++tim][0]=x;
		d[x]=d[par[x]]+1;
		for(int i=0;i<(int)G[x].size();i++){
			dfs(G[x][i]);
			f[++tim][0]=x;
		}
	}
	int RMQ_min(int l,int r){
		if(l>r)swap(l,r);
		int k=log_tbl[r-l+1];
		return d[f[l][k]]<d[f[r-(1<<k)+1][k]]?f[l][k]:f[r-(1<<k)+1][k];
	}
	int LCA(int x,int y){return RMQ_min(dfn[x],dfn[y]);}
	int LCP(int i,int j){return val[LCA(iter[i],iter[j])];}
}SAM1,SAM2;//反串和原串的后缀自动机，分别维护LCP和LCS
char s[maxn];
int T,n,ans;
int main(){
	freopen("broken.in","r",stdin);
	freopen("broken.out","w",stdout);
	scanf("%d",&T);
	while(T--){
		SAM1.clear();
		SAM2.clear();
		ans=1;
		scanf("%d",&n);
		for(int i=0;i<n;i++)scanf(" %c",&s[i]);
		for(int i=n-1;i>=0;i--)SAM1.expand(s[i]-'a',i);
		for(int i=0;i<n;i++)SAM2.expand(s[i]-'a',i);
		SAM1.LCP_init();
		SAM2.LCP_init();
		for(int L=1;L<=n;L++)for(int i=0;i+L<n;i+=L)
			ans=max(ans,(SAM1.LCP(i,i+L)+SAM2.LCP(i,i+L)-1)/L+1);
		printf("%d\n",ans);
	}
	return 0;
}
/*
枚举长度L，显然如果有一个长为L的子串重复出现，那么一定会包含s[k*L]中的至少两个，
对正反串各建一个后缀自动机，然后预处理LCA后O(1)回答LCP和LCS(最长公共后缀)即可。
LCA的话可以用ST，那么总的复杂度就是O(nlogn)。
*/