Abc 375 D - ABA

问题陈述

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

求满足以下两个条件的整数三元组 (i,j,k) 的个数：

1≤i<j<k≤∣S∣

按此顺序连接 Si、Sj 和 Sk 所形成的长度为 3 的字符串是一个回文字符串。

这里，∣S∣ 表示 S 的长度，Sx 表示 S 的第 x 个字符。

限制条件

S 是长度介于 和 2×10 5 之间的字符串，由大写英文字母组成。

输入

输入由标准输入法提供，格式如下：

S

输出

打印答案。

输入示例 1

ABCACC

样本输出 1

5

满足条件的三元组为 (i,j,k)=(1,2,4),(1,3,4),(3,4,5),(3,4,6),(3,5,6).

输入示例 2

OOOOOOOO

样本输出 2

56

样本输入 3

XYYYXYYXYXXX

样本输出 3

75

----

这道题是固定中间的元素，然后查找两边相同元素的数量，乘积累加即可。我怎么就想不到了。。。其实就是前缀和跟后缀和的处理。