Algorithm
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.
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 the only number — the sum of the polindrome degrees of all the string's prefixes.
a2A
1
abacaba
6
Code Examples
#1 Code Example with C++ Programming
Code -
C++ Programming
#include <bits/stdc++.h>
using namespace std;
int const N = 5e6 + 1;
int const p = 67;
int const m = 1e9 + 9;
char s[N];
int n, res[N];
long long hash_value[N][2];
long long p_pow[N];
long long compute_hash() {
p_pow[0] = 1;
for(int i = 1; i < N; ++i)
p_pow[i] = (p_pow[i - 1] * p) % m;
if(islower(s[0]))
hash_value[0][0] = ((s[0] - 'a' + 1) * p_pow[0]) % m;
else if(isupper(s[0]))
hash_value[0][0] = ((s[0] - 'A' + 27) * p_pow[0]) % m;
else
hash_value[0][0] = ((s[0] - '0' + 53) * p_pow[0]) % m;
for(int i = 1; i < n; ++i) {
if(islower(s[i]))
hash_value[i][0] = (hash_value[i - 1][0] + (s[i] - 'a' + 1) * p_pow[i]) % m;
else if(isupper(s[i]))
hash_value[i][0] = (hash_value[i - 1][0] + (s[i] - 'A' + 27) * p_pow[i]) % m;
else
hash_value[i][0] = (hash_value[i - 1][0] + (s[i] - '0' + 53) * p_pow[i]) % m;
}
if(islower(s[n - 1]))
hash_value[n - 1][1] = ((s[n - 1] - 'a' + 1) * p_pow[0]) % m;
else if(isupper(s[n - 1]))
hash_value[n - 1][1] = ((s[n - 1] - 'A' + 27) * p_pow[0]) % m;
else
hash_value[n - 1][1] = ((s[n - 1] - '0' + 53) * p_pow[0]) % m;
for(int i = n - 2; i >= 0; --i) {
if(islower(s[i]))
hash_value[i][1] = (hash_value[i + 1][1] + (s[i] - 'a' + 1) * p_pow[n - i - 1]) % m;
else if(isupper(s[i]))
hash_value[i][1] = (hash_value[i + 1][1] + (s[i] - 'A' + 27) * p_pow[n - i - 1]) % m;
else
hash_value[i][1] = (hash_value[i + 1][1] + (s[i] - '0' + 53) * p_pow[n - i - 1]) % m;
}
}
bool is_pal(int idx) {
long long first_hash = hash_value[idx][0];
long long second_hash = (hash_value[0][1] - hash_value[idx + 1][1] + m) % m;
first_hash = (first_hash * p_pow[(n - idx - 1)]) % m;
return first_hash == second_hash;
}
int main() {
scanf("%s", s);
n = strlen(s);
compute_hash();
res[0] = 1;
for(int i = 1; i < n; ++i)
if(is_pal(i))
res[i] = res[i / 2 - !(i & 1)] + 1;
int to = 0;
for(int i = 0; i < n; ++i)
to += res[i];
printf("%d\n", to);
return 0;
}Input
Output
Demonstration
Codeforcess Solution Palindrome Degree D. Palindrome Degree,C,C++, Java, Js and Python ,D. Palindrome Degree,Codeforcess Solution