Problem2836--最美字符串

2836: 最美字符串

Time Limit: 1 Sec  Memory Limit: 128 MB
Submit: 93  Solved: 44
[Submit] [Status] [Web Board] [Creator:]

Description

我们对于字符串的完美度进行了如下定义:
对于一个n长度的字符串,一定有(n+1)*n/2个子串
完美度是其所有回文子串的数量
例如,字符串“anacana”拥有以下回文子串
"a","n","a","c","a","n","a","ana","aca","ana","nacan","anacana",共12个
所以说该字符串的完美度即为12.

Input

输入为若干个字符串
每个字符串一行,每个字符串长度len<11000.


Output

输出每个字符串的完美度
每个输出占一行

Sample Input Copy

anacana
11211

Sample Output Copy

12
9

HINT

本题数据较小,尝试使用哈希解决吧!

Source/Category