← 返回题目列表

Codeforces · 159/D

D. 回文对

中文机器翻译题面 查看原题

给你一个由小写字母组成的非空字符串 s 。求该字符串的非重叠回文子串对的数量。

以更正式的方式,您必须找到元组 (a, b, x, y) 的数量,使得 1 ≤ a ≤ b < x ≤ y ≤ |s|子串 s[a...b]、s[x...y] 是回文。

回文是一个可以从左到右和从右到左以相同方式读取的字符串。例如,“abacaba”、“z”、“abba”是回文。

字符串 s = s1s2... s|s| 的子串 s[i... j] (1 ≤ i ≤ j ≤ |s|)是一个字符串 sisi + 1... sj。例如,字符串 s = "abacaba" 的子字符串 s[2...4] 等于 "bac"。

输入

第一行输入包含一个由小写字母('a'...'z')组成的非空字符串 s,s 最多包含 2000 个字符。

输出

输出一个数字 — s 的非重叠回文子串对的数量。

请不要使用 %lld 格式说明符在 С++ 中读取或写入 64 位整数。最好使用 cin、cout 流或 %I64d 格式说明符。

示例

输入 #1

aa

输出 #1

1

输入 #2

aaa

输出 #2

5

输入 #3

abacaba

输出 #3

36