C - C Stands for Center Editorial /

Time Limit: 2 sec / Memory Limit: 1024 MiB

配点 : 300 点

問題文

英大文字からなる文字列 S が与えられます。
以下の条件を全て満たす S の部分文字列 (連続する部分列) がいくつあるか求めてください。

  • 奇数個の文字からなる。
  • 中央の文字が C である。厳密には、抜き出した部分文字列が l 文字からなるとき、その (l+1)/2 文字目が C である。

ただし、部分文字列が文字列として一致していても、抜き出した文字の位置が異なる場合、それぞれ別に数えます。

制約

  • S は英大文字からなる長さ 1 以上 5 \times 10^5 以下の文字列

入力

入力は以下の形式で標準入力から与えられる。

S

出力

答えを出力せよ。

入力例 1

ABCCA

出力例 1

5

この入力では、 S= ABCCA です。
問題文中の条件を満たす部分文字列は以下の 5 つです。

  • S 中の 1 文字目から 5 文字目までを抜き出した ABCCA
  • S 中の 2 文字目から 4 文字目までを抜き出した BCC
  • S 中の 3 文字目から 3 文字目までを抜き出した C
  • S 中の 3 文字目から 5 文字目までを抜き出した CCA
  • S 中の 4 文字目から 4 文字目までを抜き出した C

入力例 2

XYZ

出力例 2

0

入力例 3

SMBCPROGRAMMINGCONTEST

出力例 3

11

Score : 300 points

Problem Statement

You are given a string S consisting of uppercase English letters.
Find the number of substrings (contiguous subsequences) of S that satisfy all of the following conditions.

  • It consists of an odd number of characters.
  • Its middle character is C. More formally, if the extracted substring consists of l characters, its ((l+1)/2)-th character is C.

Even if two substrings are identical as strings, they are counted separately if they are extracted from different positions.

Constraints

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

Input

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

S

Output

Output the answer.

Sample Input 1

ABCCA

Sample Output 1

5

In this input, S= ABCCA.
The substrings satisfying the conditions in the problem statement are the following five:

  • ABCCA, extracted from the 1st to 5th characters of S
  • BCC, extracted from the 2nd to 4th characters of S
  • C, extracted from the 3rd to 3rd characters of S
  • CCA, extracted from the 3rd to 5th characters of S
  • C, extracted from the 4th to 4th characters of S

Sample Input 2

XYZ

Sample Output 2

0

Sample Input 3

SMBCPROGRAMMINGCONTEST

Sample Output 3

11