4237: Palindrome Degree
内存限制：256 MB
时间限制：2 S
标准输入输出
题目类型：传统
评测方式：文本比较
上传者：
提交：1
通过：1
题目描述
time limit per test
1 secondmemory limit per test
256 megabytesinput
standard inputoutput
standard outputString 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.
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
输入样例 复制
输出样例 复制