← 返回题目列表

AtCoder · abc375_d

G. 阿巴

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

分数: 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