[SPOJ 687] 重复的字符串 - HouJikan - 155867

记录编号	155867	评测结果	AAAAAAAAAA
题目名称	[SPOJ 687] 重复的字符串	最终得分	100
用户昵称	HouJikan	是否通过	通过
代码语言	C++	运行时间	9.935 s
提交时间	2015-03-31 16:49:25	内存使用	10.91 MiB
显示代码纯文本
#include <iostream>
#include <cstring>
#include <string>
#include <cstdio>
#include <cstdlib>
#include <cmath>
#include <algorithm>
#include <queue>
#include <stack>
#include <map>
#include <set>
#include <list>
#include <vector>
#include <ctime>
#include <functional>
#define pritnf printf
#define scafn scanf
#define sacnf scanf
#define For(i,j,k) for(int i=(j);i<=(k);(i)++)
#define Clear(a) memset(a,0,sizeof(a))
using namespace std;
typedef unsigned int Uint;
const int INF=0x3fffffff;
const double eps=1e-10;
///==============struct declaration==============

///==============var declaration=================
const int MAXN=60010;
int T,n,k;
int srank[MAXN],prank[MAXN],sa[MAXN],trank[MAXN],h[MAXN],pa[MAXN];
char str[MAXN];
int PRMQ[20][MAXN],SRMQ[20][MAXN];
///==============function declaration============
bool cmp1(int a,int b){return str[a]<str[b];}
bool cmp2(int a,int b){return srank[a]==srank[b]?srank[a+(1<<k)]<srank[b+(1<<k)]:srank[a]<srank[b];}
bool cmp3(int a,int b){return prank[a]==prank[b]?prank[a+(1<<k)]<prank[b+(1<<k)]:prank[a]<prank[b];}
void SuffixArray();void PreffixArray();
int LCP(int a,int b);int LCS(int a,int b);
///==============main code=======================
int main()
{
	//#define FILE__
	//#ifdef FILE__
   freopen("repeats.in","r",stdin);
   freopen("repeats.out","w",stdout);
	//#endif 
	scanf("%d",&T);
	while (T--){
		int _ans=0;
		scanf("%d",&n);memset(SRMQ,0,sizeof(SRMQ));memset(PRMQ,0,sizeof(PRMQ));
		memset(srank,0,sizeof(srank));memset(prank,0,sizeof(prank));memset(str,0,sizeof(str));
		for(int i=1;i<=n;i++){
			//getchar();
			str[i]=getchar();
			while (str[i]!='a'&&str[i]!='b')
				str[i]=getchar();
		}
		str[n+1]='$';n++;
		SuffixArray();n--;
		for(int i=1;i<=n/2;i++)swap(str[i],str[n-i+1]);n++;
		PreffixArray();
		for(int length=1;length<=n/2;length++)
			for(int i=1;i+length<=n;i+=length){
				int x=LCP(i,i+length);
				int y=LCS(n-i,n-(i+length));
				_ans=max(_ans,(x+y-1)/length+1);
			}
		if (_ans==0) _ans=1;
		printf("%d\n",_ans);
	}
   return 0;
}
///================fuction code====================
void SuffixArray(){
	for(int i=1;i<=n;i++)
		sa[i]=i;
	sort(sa+1,sa+1+n,cmp1);
	srank[sa[1]]=1;
	for(int i=2;i<=n;i++)
		if (str[sa[i-1]]==str[sa[i]])
			srank[sa[i]]=srank[sa[i-1]];
		else
			srank[sa[i]]=srank[sa[i-1]]+1;
	for(k=0;(1<<k)<=n;k++){
		sort(sa+1,sa+1+n,cmp2);
		trank[sa[1]]=1;
		for(int i=2;i<=n;i++)
			if (srank[sa[i]]==srank[sa[i-1]]&&srank[sa[i]+(1<<k)]==srank[sa[i-1]+(1<<k)])
				trank[sa[i]]=trank[sa[i-1]];
			else
				trank[sa[i]]=trank[sa[i-1]]+1;
		for(int i=1;i<=n;i++)
			srank[i]=trank[i];
		if (srank[sa[n]]==n) break;
	}
	for(int i=1;i<=n;i++)
		srank[sa[i]]=i;
	for(int i=1;i<=n;i++){
		h[srank[i]]=max(h[srank[i-1]]-1,0);
		int p=i,q=sa[srank[i]-1];
		while (str[p+h[srank[i]]]==str[q+h[srank[i]]])
			h[srank[i]]++;
	}
	for(int i=1;i<=n;i++)
		SRMQ[0][i]=h[i];
	for(k=1;(1<<k)<=n;k++)
		for(int i=1;(i+(1<<(k-1)))<=n;i++)
			SRMQ[k][i]=min(SRMQ[k-1][i],SRMQ[k-1][i+(1<<(k-1))]);
}
void PreffixArray(){
	for(int i=1;i<=n;i++)
		pa[i]=i;
	sort(pa+1,pa+1+n,cmp1);
	prank[pa[1]]=1;
	for(int i=2;i<=n;i++)
		if (str[pa[i-1]]==str[pa[i]])
			prank[pa[i]]=prank[pa[i-1]];
		else
			prank[pa[i]]=prank[pa[i-1]]+1;
	for(k=0;(1<<k)<=n;k++){
		sort(pa+1,pa+1+n,cmp3);
		trank[pa[1]]=1;
		for(int i=2;i<=n;i++)
			if (prank[pa[i]]==prank[pa[i-1]]&&prank[pa[i]+(1<<k)]==prank[pa[i-1]+(1<<k)])
				trank[pa[i]]=trank[pa[i-1]];
			else
				trank[pa[i]]=trank[pa[i-1]]+1;
		for(int i=1;i<=n;i++)
			prank[i]=trank[i];
		if (prank[pa[n]]==n) break;
	}
	for(int i=1;i<=n;i++)
		prank[pa[i]]=i;
	for(int i=1;i<=n;i++){
		h[prank[i]]=max(h[prank[i-1]]-1,0);
		int p=i,q=pa[prank[i]-1];
		while (str[p+h[prank[i]]]==str[q+h[prank[i]]])
			h[prank[i]]++;
	}
	for(int i=1;i<=n;i++)
		PRMQ[0][i]=h[i];
	for(k=1;(1<<k)<=n;k++)
		for(int i=1;((i+(1<<(k-1))))<=n;i++)
			PRMQ[k][i]=min(PRMQ[k-1][i],PRMQ[k-1][i+(1<<(k-1))]);
}
int LCP(int a,int b){
	a=srank[a],b=srank[b];
	if (b<a) swap(a,b);
	a++;
	int length=b-a+1;
	if (length==1) return SRMQ[0][a];
	int k=0,x=1;
	while (x<length){
		k++;
		x<<=1;
	}
	k--;
	return min(SRMQ[k][a],SRMQ[k][a+(1<<k)]);
}
int LCS(int a,int b){
	a=prank[a],b=prank[b];
	if (b<a) swap(a,b);
	a++;
	int length=b-a+1;
	int k=0,x=1;
	if (length==1) return PRMQ[0][a];
	while (x<length){
		k++;
		x<<=1;
	}
	k--;
	return min(PRMQ[k][a],PRMQ[k][a+(1<<k)]);
}