spoj687 REPEATS

転送ゲート:http://www.spoj.com/problems/REPEATS/
考え方:また論文の問題です.
論文ではこう言っています
この問題は長さを列挙する方法を用いて、後で私たちが2つの接尾辞のLCPを見るだけでいいのに対して、前にマッチングして、1つの明らかな方法は列を逆にして、後ろに対応する接尾辞のLCPを受け取ることです.実際にはそうする必要はありません.私たちはまだいくつかの文字が足りないのを見るだけで循環回数に1を加えることができます.では、私たちはこんなに多くの人を前に移動して、この2つの接尾辞のLCPの長さが十分かどうかを見て、十分に1を加えることができます(せいぜい1を加えるだけです.2を加えると、この答えは前回の列挙で統計されますから).

#include<cmath>
#include<cstdio>
#include<cstring>
#include<algorithm>
const int maxn=100010;
using namespace std;
int T,n,t1[maxn],t2[maxn],sum[maxn],rank[maxn],sa[maxn],st[maxn][20],h[maxn],maxs;char s[maxn],c[5];

void getsa(){
	memset(sum,0,sizeof(sum));
	int *x=t1,*y=t2,m=255,p=0;
	for (int i=1;i<=n;i++) sum[x[i]=s[i]]++;
	for (int i=1;i<=m;i++) sum[i]+=sum[i-1];
	for (int i=n;i;i--) sa[sum[x[i]]--]=i;
	for (int j=1;p<n;j<<=1,m=p){
		p=0;
		for (int i=n-j+1;i<=n;i++) y[++p]=i;
		for (int i=1;i<=n;i++) if (sa[i]>j) y[++p]=sa[i]-j;
		memset(sum,0,sizeof(sum));
		for (int i=1;i<=n;i++) sum[x[y[i]]]++;
		for (int i=1;i<=m;i++) sum[i]+=sum[i-1];
		for (int i=n;i;i--) sa[sum[x[y[i]]]--]=y[i];
		swap(x,y),x[sa[1]]=p=1;
		for (int i=2;i<=n;i++){
			if (y[sa[i]]!=y[sa[i-1]]||y[sa[i]+j]!=y[sa[i-1]+j]) p++;
			x[sa[i]]=p;
		}
	}
	memcpy(rank,x,sizeof(rank));
}

void geth(){
	for (int i=1,j=0;i<=n;i++){
		if (rank[i]==1) continue;
		while (s[i+j]==s[sa[rank[i]-1]+j]) j++;
		h[rank[i]]=j;
		if (j) j--;
	}
}

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

int getmin(int x,int y){
	int l=rank[x],r=rank[y];
	if (l>r) swap(l,r);
	l++;int k=log2(r-l+1);//     ++l
	return min(st[l][k],st[r-(1<<k)+1][k]);
}

int main(){
	scanf("%d",&T);
	while (T--){
		scanf("%d",&n);maxs=0;
		for (int i=1;i<=n;i++) scanf("%s",c),s[i]=c[0];
		s[n+1]=0,getsa(),geth(),getst();
		for (int i=1;i<=n;i++)
			for (int j=1;j+i<=n;j+=i){
				int tmp=getmin(j,j+i),k=j-(i-tmp%i);
				tmp/=i;
				if (k>=0&&getmin(k,k+i)>=i) tmp++;//    i         (i-tmp%i)，             ，         。
				maxs=max(maxs,tmp+1);
			}
		printf("%d
",maxs);
	}
	return 0;
}