#7 D. Palindrome Degree （manacher + dp）

落日映苍穹つ 2022-06-17 01:46 129阅读 0赞

题目链接：

[点击打开链接][Link 1]

http://codeforces.com/contest/7/problem/D

D. Palindrome Degree

String *s* of length *n* is called *k*\-palindrome, if it is a palindrome itself, and its prefix and suffix of length ![76a32f1d342721f3d342500117034480c296f100.png][] are (*k* - 1)\-palindromes. By definition, any string (even empty) is 0-palindrome.

Let's call the palindrome degree of string *s* such a maximum number *k*, for which *s* is *k*\-palindrome. For example, "abaaba" has degree equals to3.

You are given a string. Your task is to find the sum of the palindrome degrees of all its prefixes.

Input

The first line of the input data contains a non-empty string, consisting of Latin letters and digits. The length of the string does not exceed 5·106. The string is case-sensitive.

Output

Output the only number — the sum of the polindrome degrees of all the string's prefixes.

Examples

input

a2A

output

input

abacaba

output

题意：

设Degree的定义为：

每个串（包括空串）的等级至少为0.

若一个长度为len的前缀是回文串，且它的一个长度为floor(len/2)的前缀和后缀的“Degree”为k，

则他的“Degree”是k+1。

其余一个字符串所有前缀的“Degree”的和。

题解：

用manacher算法处理出最左端为第一个字母的所有回文串，然后dp一下。

dp\[i\]表示长度为i的前缀是k-回文串（k=dp\[i\])。 则dp\[i\]=dp\[i/2\]+1;

ans=sigma(dp\[i\])。

AC代码：

#include<bits/stdc++.h>
    using namespace std;
    typedef long long ll;
    const int N=5e6+7;
    char str[N<<1],s[N];
    int p[N<<1];
    int n,len;
    ll dp[N];
    
    ll Manacher()
    {
        int i,j,id,mx;
        ll ans=0;
        id=0,mx=1;
        p[0]=p[1]=1;
        for(i=0;i<n;i++)
    	{
            p[i]=1;
            if(mx>i){
                p[i]=min(p[(id<<1)-i],mx-i);
            }
            int k=i+p[i];  //.....
            while(str[i+p[i]]==str[i-p[i]]) k++,p[i]++; //.....
            if(i+p[i]>mx){
                id=i;
                mx=i+p[i];
            }
            /********************/
            if(2*i-k==0 && i>1){
            	int l=p[i]-1;
                dp[l]=dp[l/2]+1;
                ans += dp[l];
    		}
    		/********************/
        }
        return ans;
    }
    
    
    void getstr()
    {
       str[0]='$';
       str[n]='#';
       str[n+1]='\0';
        for(int i=len*2;i>=1;--i)
    	{
            if(i&1) str[i]='#';
            else str[i]=str[i/2];
        }
    }
    
    
    int main()
    {
    	scanf("%s",str+1);
    	
    	len=strlen(str+1);
    	n=2*len+1;
    	getstr();
    //	puts(str);
    	memset(dp,0,sizeof(dp));
    	ll ans =Manacher();
    	cout<<ans<<endl;
    	return 0;
    }
    /*
    a2A
    1
    
    abacaba
    6
    */

[Link 1]: http://codeforces.com/contest/7/problem/D
[76a32f1d342721f3d342500117034480c296f100.png]: /images/20220617/5d2880e864334f97a2f93a2ec2cc524e.png