题目描述

给定一个非空字符串 $s$，该字符串由小写字母组成。请你计算该字符串中不重叠的回文子串对的数量。

更正式地说，你需要求出四元组 $(a, b, x, y)$ 的个数，使得 $1 \le a \le b < x \le y \le |s|$，并且子串 $s[a...b]$ 与 $s[x...y]$ 均为回文串。

回文串是指正着读和反着读都相同的字符串。例如，"abacaba"、"z"、"abba" 都是回文串。

字符串 $s[i...j]$（$1 \le i \le j \le |s|$）是字符串 $s = s_1s_2...s_{|s|}$ 的一个子串，表示 $s_is_{i+1}...s_j$。例如，字符串 $s =$"abacaba" 的子串 $s[2...4]$ 为 "bac"。

输入格式

输入的第一行包含一个非空字符串 $s$，由小写字母（'a' 到 'z'）组成。

输出格式

输出一个整数，表示字符串 $s$ 中所有不重叠回文子串对的数量。

请不要在 C++ 中使用 %lld 格式说明符进行 64 位整数的输入输出。推荐使用 cin、cout 流或 %I64d 格式说明符。

aa

1

aaa

5

abacaba

36

说明 / 提示

由 ChatGPT 5 翻译

数据范围

$s$ 最多包含 $2000$ 个字符。