回文串计数

Grade 0 Open Time Friday, 28 December 2012, 6:40 pm
Discount 0.8 Time Discount Friday, 28 December 2012, 6:40 pm
Allow late Yes Close Time Friday, 28 December 2012, 6:40 pm
Input file calc.in Output file calc.out

【题目描述】

虽然是一名理科生,Mcx常常声称自己是一名真正的文科生。不知为何,他对于背诵总有一种莫名的热爱,这也促使他走向了以记忆量大而闻名的生物竞赛。然而,他很快发现这并不能满足他热爱背诵的心,但是作为一名强大的Boer,他找到了这么一条自虐的方式——背诵基因序列。不过这实在是太虐心了,就连Mcx也有些招架不住。不过他发现,如果他能事先知道这个序列里有多少对互不相交的回文串,他或许可以找到记忆的妙法。为了进一步验证这个方法,Mcx决定选取一个由小写字母构成的字符串SS来实验。不过由于互不相交的回文串实在过多,他很快就数晕了。不过他相信,在你的面前这个问题不过是小菜一碟。

【名词解释】

1.对于字符串SS,设其长度为Len,那么下文用Si表示SS中第i个字符(1<=i<=Len)

2.s[i,j]表示SS的一个子字串,s[i,j] = “SiSi+1Si+2…Sj-2Sj-1Sj”,比如当SS”abcgfd”时,

s[2,5] = “bcgf” , s[1,5] = “abcgf”

3.当一个串被称为一个回文串当且仅当将这个串反写后与原串相同,如”abcba”

4.考虑一个四元组(l,r,L,R) s[l,r]s[L,R]均为回文串时,且满足1 <= l <=r< L <= R <= Len时,我们称s[l,r]s[L,R]为一对互不相交的回文串。本题要求这种四元组的个数。两个四元组相同当且仅当对应的l,r,L,R都相同。

【题目输入】

仅一行,为字符串SS,保证全部由小写字母构成,由换行符标志结束。

【题目输出】

仅一行,为一个整数,表示互不相交的回文串的对数。

【样例输入】

aaa

【样例输出】

5

【样例解释】

SS = “aaa” , SS的任意一个字串均为回文串,其中总计有5对互不相交的回文串:

(1,1,2,2) , (1,1,2,3) , (1,1,3,3) , (1,2,3,3) , (2,2,3,3).  (这里使用名词解释中的四元组进行表示)

【数据范围】

50%的数据满足SS的长度不超过200

100%的数据满足SS的长度不超过2000