B去--K 级别的回文串

Time Limit: 1000 ms Memory Limit: 65536 KiB

Problem Description

新年伊始,我飞的得到了一个字符串,时尚时尚最时尚回文肯定棒。现在我飞要在这个字符串上搞一些事情。

现在有如下定义:

对于一个长度为n的字符串T,如果T是回文的,且T的长度为n/2的前缀Pre和后缀Suf都是(k-1)级别的回文串,我们则称T为K级别的回文串。另,如果T是一个空串或者T不是回文串,则T为0级别的回文串。

那么现在问题来了,给出一个SS的所有前缀的级别之和为多少?

abaaba”的前缀a”ab”aba”abaa”abaab”abaaba”的级别各为102003,故其前缀级别之和为6

Input

  多组输入,对于每组数据:
  输入只有一行,包含一个字符串S,1 <= length(S) <= 10^5S只包含大小写字母与数字。

 

Output

 对于每组数据输出一个整数代表答案。

Sample Input

abaaba
abca

Sample Output

6
1

Hint

 

Source

zmx