AT_abc375_d [ABC375D] ABA

题目描述

给定一个由大写英文字母组成的字符串 $S$。

请你求出满足以下条件的整数三元组 $(i,\ j,\ k)$ 的个数。

• $1 \leq i < j < k \leq |S|$。
• 将 $S_i$、$S_j$、$S_k$ 按顺序连接得到的长度为 $3$ 的字符串是回文串。

其中，$|S|$ 表示字符串 $S$ 的长度，$S_x$ 表示 $S$ 的第 $x$ 个字符。

输入格式

输入为标准输入，格式如下：

$S$

输出格式

输出满足条件的三元组个数。

输入输出样例 #1

输入 #1

ABCACC

输出 #1

5

输入输出样例 #2

输入 #2

OOOOOOOO

输出 #2

56

输入输出样例 #3

输入 #3

XYYXYYXYXXX

输出 #3

75

说明/提示

限制

• $S$ 是一个长度不少于 $1$ 且不超过 $2 \times 10^5$ 的大写英文字母字符串。

样例解释 1

$(i,\ j,\ k) = (1,\ 2,\ 4),\ (1,\ 3,\ 4),\ (3,\ 4,\ 5),\ (3,\ 4,\ 6),\ (3,\ 5,\ 6)$ 满足条件。

由 ChatGPT 4.1 翻译