No.464 PPAP

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

3 ProblemId : 1447 / 出題時の順位表

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

注意

想定解法では、C++14, PyPy3, PyPy2, Java8 (テスターさんによるコード) で AC することを確認していますが、素の Python では TLE しています。
ご了承下さい。

問題文

$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 5000$
  • $S$ は半角英小文字のみから成る

出力

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

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

サンプル

サンプル1
入力
abcd
出力
1

(a, b, c, d) の $1$ 通りです。

サンプル2
入力
ababababa
出力
10
以下の $10$ 通りです。
  • (a, b, ab, ababa)
  • (a, b, abab, aba)
  • (a, b, ababab, a)
  • (a, bab, ab, aba)
  • (a, bab, abab, a)
  • (a, babab, ab, a)
  • (aba, b, ab, aba)
  • (aba, b, abab, a)
  • (aba, bab, ab, a)
  • (ababa, b, ab, a)
サンプル3
入力
penpineappleapplepen
出力
1

(p, e, npineappleapplepe, n) の $1$ 通りです。

サンプル4
入力
mississippi
出力
5
以下の $5$ 通りです。
  • (m, i, ssiss, ippi)
  • (m, i, ssissipp, i)
  • (m, issi, ss, ippi)
  • (m, issi, ssipp, i)
  • (m, ississi, pp, i)
提出ページヘ