#P1872. 回文串计数

回文串计数

题目描述

aa 虽然是一名理科生,但他常常称自己是一名真正的文科生。不知为何,他对于背诵总有一种莫名其妙的热爱,这也促使他走向了以记忆量大而闻名的生物竞赛。然而,他很快发现这并不能满足他热爱背诵的心,但是作为一名强大的 OIER,他找到了这么一个方法——背诵基因序列。然而这实在是太困难了,小啊感觉有些招架不住。

不过他发现,如果他能事先知道这个序列里有多少对互不相交的回文串,他或许可以找到记忆的妙法。为了进一步验证这个想法,小 aa 决定选取一个由小写字母构成的字符串 SSSS 来实验。由于互不相关的回文串实在过多,他很快就数晕了。不过他相信,在你的面前这个问题不过是小菜一碟。

  1. 对于字符串 SSSS,设其长度为 Len,那么下文用 SiS_i 表示 SSSS 中第 ii 个字符(1iLen1 \le i \le Le_n)。

  2. S[i,j]S[i,j] 表示 SSSS 的一个子串,$S[i,j]=S_i S_{i+1}S_{i+2} \cdots S_{j-2}S_{j-1}S_{j}$,比如当 SSSSabcgfd 时,S[2,5]S[2,5] 就是 bcgfS[1,5]S[1,5]abcgf

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

  4. 考虑一个四元组 (l,r,L,R)(l,r,L,R),当 S[l,r]S[l,r]S[L,R]S[L,R] 均为回文串时,且满足 1lr<LRLen1 \le l \le r<L \le R \le \text{Len} 时,我们称 S[l,r]S[l,r]S[L,R]S[L,R] 为一对互不相交的回文串。即本题所求,也即为这种四元组的个数。两个四元组相同当且仅当对应的 l,r,L,Rl,r,L,R 都相同。

输入格式

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

5050 %的数据满足 SSSS 的长度不超过 200200

100100 %的数据满足 SSSS 的长度不超过 20002000

输出格式

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

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)。