PKU 1961-Period

PKU

問題概要

長さが106以下の文字列が与えられるので，その全ての接頭辞について，文字列の最大繰り返し数を求めよ．

解法

考えられる繰り返し文字列の長さi(1<=i<=n/2)について，愚直に調べました．
ただしそのままでは間に合わないので以下の二つの枝刈りをしました．

  • 2つの文字列の比較にハッシュを使いO(1)で比較出来るようにする．
  • k番目の文字までを見た時の最大繰り返し数をA(k)とすると，A(k/A(k))=1となるので，A(i)>1の時は調べない．

ところで

KMPを使う解法が普通みたいです．
詳しくはid:Respect2Dさんの記事( http://d.hatena.ne.jp/Respect2D/20110805/1312562316 )を見てください．

実装(C++)

#include <cstdio>
#include <algorithm>
#include <cstring>
#include <iostream>
using namespace std;
char a[1000001];
int ans[1000001];
int hash[1000001];
int n;
const int MOD=1000000009;
const int HV=67;
int rev[1000001];
inline int calc(int s,int e){
	int val=(hash[e]-hash[s]+MOD)%MOD;
	return (long long)val*rev[s]%MOD;
}
long long mod_pow(long long a,long long n,long long M){
	if(n==0)return 1%M;
	long long res=mod_pow(a*a%M,n/2,M);
	if(n&1)res=res*a%M;
	return res;
}
int main(int testcase) {
	rev[0]=1;
	for(int i=1;i<1000001;i++){
		rev[i]=((long long)rev[i-1]*HV)%MOD;
	}
	for(int i=1;i<1000001;i++){
		rev[i]=mod_pow(rev[i],MOD-2,MOD);
	}
	while(scanf("%d",&n),n){
		scanf("%s",a);
		hash[0]=0;
		for(int i=1;i<=n;i++){
			hash[i]=((long long)HV*hash[i-1]+a[i-1])%MOD;
		}
		memset(ans,0,sizeof(ans));
		for(int i=1;i<=n/2;i++){ //繰り返し文字列の長さ（<=n/2)
			if(ans[i-1]>1)continue; //a[i]>1なら調べない
			for(int j=i;j+i<=n;j+=i){
				bool ok=true;
				if(calc(0,i)!=calc(j,j+i)){
					break; //ハッシュが一致していない
				}
				for(int k=0;k<i;k++){
					if(a[k]!=a[k+j]){
						ok=false;
						break;
					}
				}
				if(!ok)break;
				ans[j+i-1]=j/i+1;
			}
		}
		printf("Test case #%d\n",testcase++);
		for(int i=0;i<n;i++){
			if(ans[i]>1){
				printf("%d %d\n",i+1,ans[i]);
			}
		}
		printf("\n");
	}
	return 0;
}