C - 1122 Substring 2 解説 /

実行時間制限: 2 sec / メモリ制限: 1024 MiB

配点 : 300 点

問題文

数字からなる文字列 S が与えられます。

以下の条件を全て満たす文字列 T を 1122文字列 と呼びます。（定義は F 問題と同じです。）

  • T は数字からなる空でない文字列
  • |T| は偶数。ここで、 |T| は文字列 T の長さを表す
  • T の 1 文字目から \frac{|T|}2 文字目までは全て同じ数字である
  • T の \frac{|T|}2+1 文字目から |T| 文字目までは全て同じ数字である
  • T の 1 文字目の数字に 1 を足すと |T| 文字目の数字になる

例えば 1122 や 01 、 444555 などは 1122文字列 ですが、 1222 や 90 は 1122文字列 ではありません。

S の 部分文字列 であって 1122文字列 であるものの個数を求めてください。

ただし、ある二つの部分文字列が文字列として同じでも、取り出された位置が異なるならばそれらは別々に数えるものとします。

制約

  • S は長さ 1 以上 10^6 以下の数字からなる文字列

入力

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

S

出力

S の空でない部分文字列であって 1122文字列 であるものの個数を出力せよ。

入力例 1

1122

出力例 1

2

以下の 2 つの部分文字列が条件を満たします。

  • S の 2 文字目から 3 文字目を取り出した 12
  • S の 1 文字目から 4 文字目を取り出した 1122

したがって、 2 を出力してください。

入力例 2

7788788

出力例 2

3

文字列として同じでも、取り出された位置が異なるならばそれらは別々に数えることに注意してください。

入力例 3

2025

出力例 3

0

1122文字列 となる部分文字列が存在しない場合もあります。

入力例 4

1112222334445556555

出力例 4

11

Score : 300 points

Problem Statement

You are given a string S consisting of digits.

A string T is called a 1122-string if it satisfies all of the following conditions. (The definition is the same as in Problem F.)

  • T is a non-empty string consisting of digits.
  • |T| is even, where |T| denotes the length of string T.
  • All characters from the 1-st through the \frac{|T|}2-th character of T are the same digit.
  • All characters from the (\frac{|T|}2+1)-th through the |T|-th character of T are the same digit.
  • Adding 1 to the digit of the 1-st character of T gives the digit of the |T|-th character.

For example, 1122, 01, and 444555 are 1122-strings, but 1222 and 90 are not 1122-strings.

Find the number of substrings of S that are 1122-strings.

Two substrings are counted separately if they are extracted from different positions, even if they are identical as strings.

Constraints

  • S is a string consisting of digits with length between 1 and 10^6, inclusive.

Input

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

S

Output

Output the number of non-empty substrings of S that are 1122-strings.

Sample Input 1

1122

Sample Output 1

2

The following two substrings satisfy the condition.

  • 12 extracted from the 2-nd through 3-rd characters of S
  • 1122 extracted from the 1-st through 4-th characters of S

Thus, output 2.

Sample Input 2

7788788

Sample Output 2

3

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

Sample Input 3

2025

Sample Output 3

0

There may be no substring that is a 1122-string.

Sample Input 4

1112222334445556555

Sample Output 4

11