[データ構造-hash]CF 7 D Palindrome Degree

1194 ワード

D. Palindrome Degree
time limit per test   1 second
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 exceed5•106. The string is case-sensitive.
Output
Output the only number — the sum of the polindrome degrees of all the string's prefixes.
Sample test(s)