No.465 PPPPPPPPPPPPPPPPAPPPPPPPP

レベル : / 実行時間制限 : 1ケース 2.000秒 / メモリ制限 : 512 MB / 通常問題
タグ : / 解いたユーザー数 8
作問者 : uwiuwi / テスター : しらっ亭しらっ亭

1 ProblemId : 1467 / 出題時の順位表

この問題は Advent Calendar Contest 2016 の15日目の問題です。

問題文

$P_1, P_2, P_3$ を$1$文字以上の任意の回文、$A$ を $1$ 文字以上の任意の文字列とします。

文字列 $S$ が入力から与えられます。

$P_1, P_2, A, P_3$ をこの順に連結して得られる文字列を $PPAP$ としたとき、$PPAP = S$ となるような $(P_1, P_2, A, P_3)$ の組は何通りあるでしょうか。

入力

S
  • 1行目に文字列 $S$ が与えられる
  • $4 \le |S| \le 500000$
  • $S$ は半角英小文字のみから成る

出力

答えの整数を1行で出力してください。

最後に改行してください。

サンプル

サンプル1
入力
testsetlevelisminim
出力
8
以下の $8$ 通りです。
  • (t, e, stsetlevelis, minim)
  • (t, e, stsetlevelismini, m)
  • (t, estse, tlevelis, minim)
  • (t, estse, tlevelismini, m)
  • (testset, l, evelis, minim)
  • (testset, l, evelismini, m)
  • (testset, level, is, minim)
  • (testset, level, ismini, m)
サンプル2
入力
xxoxxxxoxxoxxoxxxxoxxxxoxxxxoxxoxxoxxxxoxx
出力
92
サンプル3
入力
ppppppppppppppppapppppppp
出力
1009
提出ページヘ