Palindrome Degree (Codeforces 7D)
Tags: Others, hashing

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.


Sample Inputs:
a2A

abacaba

Sample Outputs:
1

6

Solution (Python):
ss = input()
n = len(ss)
dp = [0 for i in range(n)]
dp[0] = 1
factor = 123
factor_now = 1
M = 1000000007
prefix = reprefix = ord(ss[0])
for i in range(1, n):
    prefix = (prefix * factor + ord(ss[i])) % M
    factor_now = factor_now * factor % M
    reprefix = (reprefix + ord(ss[i]) * factor_now) % M
    if prefix == reprefix:
        dp[i] = dp[(i - 1) // 2] + 1
print(sum(dp))

Solution (Python):
s = input()
dp = [0] + [0] * len(s)
dp[1] = 1
pref = revpref = ord(s[0])
pow101 = 101
M = 1000000007
for i in range(2, len(s) + 1):
    pref = (pref * 101 + ord(s[i - 1])) % M
    revpref = (revpref + ord(s[i - 1]) * pow101) % M
    pow101 = pow101 * 101 % M
    if pref != revpref:
        continue
    else:
        dp[i] = dp[i // 2] + 1
print(sum(dp))

Solution (Python):
s = input()
dp = [0] + [0] * len(s)
dp[1] = 1
pref = revpref = ord(s[0])
pow101 = 101
M = 1000000007
for i in range(2, len(s) + 1):
    pref = (pref * 101 + ord(s[i - 1])) % M
    revpref = (revpref + ord(s[i - 1]) * pow101) % M
    pow101 = pow101 * 101 % M
    if pref != revpref:
        continue
    else:
        dp[i] = dp[i // 2] + 1
print(sum(dp))