Codeforces Round#7 D Palindrome Degree

カテゴリがわからないのだけれど取りあえずそれっぽいのに。
昨日のCodeforces Round#7の解けなかった奴。

出典

Codeforces Round#7 Problem D Palindrome Degree

問題概要

与えられた長さn（n≦500万）の文字列が回文であり、先頭[n/2]文字と末尾[n/2]文字がk-1回文の時、その文字列はk回文と呼ばれる。また、長さ0の文字列は0回文である。

Σ[1≦i≦n]（与えられた文字列の先頭からi文字目までがk回文となるような最大のk）の値を求めよ。

解法

Manacherのアルゴリズム+動的計画法。
Manacherのアルゴリズムは本来最長回文（与えられた文字列の連続する部分文字列のうち、回文となっている最長の部分）を求めるものであるが、最長回文を求める過程でi番目の文字を中心とする回文の"直径"を記録していくので、これにより
0-i文字目の回文判定をO(1)で行うことが出来る。（前処理のコストはO(n)）

あとはそれを記録しながら順次足していけばいい（動的計画法）。

コンテスト中に思いつくのはもう少しこういう問題解かないと無理だなあ。
以下ソース。

const int MX=5000001;
char text[MX];
int deg[MX],rad[MX*2],n,ans;

void run()
{
	gets(text);
	n=strlen(text);
	
	int rad[2*n], i, j, k;
	for(i=0,j=0;i<2*n;i+=k,j=max(j-k,0))
	{
		while(i-j>=0&&i+j+1<2*n
			&&text[(i-j)/2]==text[(i+j+1)/2])++j;
		rad[i]=j;
		for(k=1;i-k>=0&&rad[i]-k>=0&&rad[i-k]!=rad[i]-k;++k)
			rad[i+k]=min(rad[i-k],rad[i]-k);
	}
	
	ans=deg[0]=1;
	for(int i=1;i<n;i++)if(rad[i]==i+1)
	{
		deg[i]=deg[(i-1)/2]+1;
		ans+=deg[i];
	}
	cout<<(n?ans:0)<<endl;
}

最長回文についてはhttp://www.prefield.com/algorithm/string/manacher.htmlを使用。まだ理解してない。