013 - 平方連続部分文字列

時間制限 1 秒 / メモリ制限 256 MB / 得点 12 / x 0 /


TLE
1sec
MLE
256MB
得点
12

問題

古代国家イワシロでは、今年は雨がほとんど降らず、民衆は困っていました。そのため、新米神官のあなたが、リュウガサワで雨乞いの儀式をすることになりました。
雨乞いの儀式では、雨を降らせてくれる竜神様のために、祈りの書に書かれた祈りの呪文を唱えます。呪文を唱え終えると、竜神様はその呪文の中に、同じ言葉が2回続けて現れる個所がいくつあったか、あなたに尋ねます。あなたがそれを言い当てれば、祈りが成就して竜神様が雨を降らせてくれます。
たとえば、あなたがababababという呪文を唱えたら、その中に現れる同じ言葉が2回続けて現れる箇所は、以下の6箇所になります。

  • 1文字目から始まるababababの1箇所(ababが2回続けて現れる)。
  • 1文字目、3文字目、5文字目からそれぞれ始まるababの3箇所(abが2回続けて現れる)。
  • 2文字目と4文字目からそれぞれ始まるbabaの2箇所(baが2回続けて現れる)。

  • 祈りを成就させるためには、どんな呪文を唱えたときも、あなたはそのような箇所の個数を正確に答えなければなりません。 文字列が与えられたとき、その中に同じ文字列が2回続けて現れる箇所の個数を求めるプログラムを作成せよ。

    入力

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

    $str$
    
    1行に英小文字からなる文字列$str$が与えられる。ただし、$str$の長さは3以上100,000以下である。

    出力

    与えられた文字列の中に同じ文字列が2回続けて現れる箇所の個数を1行に出力する。

    入出力例

    入力例1

    abababab

    出力例1

    6

    入力例2

    aaaaaaa

    出力例2

    12