B - ニコニコ文字列 Editorial /

Time Limit: 2 sec / Memory Limit: 256 MB

問題文

0 から 9 の数字から成る文字列 S が与えられます。

ある文字列 X について、X="25" または X="2525" または X="252525" …… というふうに "25" を何回か繰り返した文字列になっているとき、X はニコニコ文字列であるといいます。 たとえば "25" や "25252525" はニコニコ文字列ですが、"123" や "225" はニコニコ文字列ではありません。

あなたの仕事は、文字列 S について、ニコニコ文字列となるような連続した部分文字列の取り出し方が何通りあるかを答えることです。 文字列として同じであっても、取り出し位置が異なっていれば別々に数えます。

入力

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

S
  • 1 行目には、文字列 S が与えられる。Sの長さは 1 以上 100,000 以下である。また、S の各文字は 0 から 9 の数字のみから成る。

部分点

この問題には部分点が設定されています。

N≦2000 を満たすデータセット 1 にすべて正解すると、30 点が得られます。 追加制約のないデータセット 2 にすべて正解すると、上記のデータセットに加えてさらに 70 点が得られ、全体で 100 点が得られます。

出力

1 行目には、文字列 S からニコニコ文字列となるような連続した部分文字列を取り出す方法が何通りあるかを出力せよ。

行末の改行を忘れると不正解と判定されるので注意すること。

入力例1

2525

出力例1

3

S="2525"のケースです。部分文字列が "25" となる取り出し方が 2 通り、"2525" となる取り出し方が 1 通りあるので合計 3 通りを出力します。

入力例2

1251251252525

出力例2

8

入力例3

25225

出力例3

2

入力例4

252252252252252252

出力例4

6

入力例5

20061212

出力例5

0