D - ABA Editorial /

Time Limit: 2 sec / Memory Limit: 1024 MB

配点 : 400 点

問題文

英大文字からなる文字列 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 以上 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

Score : 400 points

Problem Statement

You are given a string S consisting of uppercase English letters.

Find the number of integer triples (i, j, k) satisfying both of the following conditions:

  • 1 \leq i < j < k \leq |S|
  • The length-3 string formed by concatenating S_i, S_j, and S_k in this order is a palindrome.

Here, |S| denotes the length of S, and S_x denotes the x-th character of S.

Constraints

  • S is a string of length between 1 and 2 \times 10^5, inclusive, consisting of uppercase English letters.

Input

The input is given from Standard Input in the following format:

S

Output

Print the answer.

Sample Input 1

ABCACC

Sample Output 1

5

The triples satisfying the conditions are (i, j, k) = (1, 2, 4), (1, 3, 4), (3, 4, 5), (3, 4, 6), (3, 5, 6).

Sample Input 2

OOOOOOOO

Sample Output 2

56

Sample Input 3

XYYXYYXYXXX

Sample Output 3

75