D. Palindrome Degree
time limit per test
1 second memory limit per test
256 megabytes input
standard input output
standard output String s of length n is called k-palindrome, if it is a palindrome itself, and its prefix and suffix of length 
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 to 3.
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
1
Input
abacaba
Output
6 （一道好题，我想到的是用manacher做，听说还可以用kmp和hash做 题意：遍历给定字符串的所有前缀，如果该前缀是个回文串，将该串对半分看还是不是个回文串，如果是，则其degree+1，如cc是个回文串，c也是个回文串，所以cc的degree==1 解题思路:跑一边manacher，用p数组判断前缀是不是回文串，如果是回文串，则它的degree是其对半分后串的degree+1。 ac代码：
1 #include2 #include 3 #include 4 #include 5 using namespace std; 6 typedef long long ll; 7 const int maxn = 5*1e6+10; 8 char st[maxn]; 9 char s[maxn<<1];10 int p[maxn<<1];11 int ans[maxn];12 void init(int le) {13 for(int i=le-1;i>=0;--i) {14 s[2*i+2]=st[i];15 s[2*i+3]='*';16 }17 s[0]='$';18 s[1]='*';19 }20 void manacher(int le) {21 int mx=0,id=0;22 for(int i=1;i<2*le+2;++i) {23 p[i]=mx>i?min(p[id*2-i],mx-i):1;24 while(s[i+p[i]]==s[i-p[i]]) p[i]++;25 if(i+p[i]>mx) {26 mx=i+p[i];27 id=i;28 }29 }30 }31 int main() {32 ll res=0;33 scanf("%s",st);34 int le = strlen(st);35 init(le);36 manacher(le);37 int u=2;38 for(int i=0;i