分数: 400 点
问题陈述
给你一个字符串 S 由大写英文字母组成。
查找整数三元组的数量 (i, j, k) 满足以下两个条件:
- 1 \leq i < j < k \leq |S|
- 长度-3 连接形成的字符串 S_i, S_j,和 S_k 这个顺序是一个回文。
在这里, |S| 表示长度 S,和 S_x 表示 x- 第一个字符 S.
约束
- S 是长度介于 1 和 2 \times 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
XYYXYYXYXXX
示例输出 3
75