No.464 PPAP
しらっ亭
uwi問題文最終更新日: 2016-12-26 00:19:29
この問題は 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)
提出するには、Twitter 、GitHub、 Googleもしくは右上の雲マークをクリックしてアカウントを作成してください。