問題一覧 > 通常問題

No.464 PPAP

レベル : / 実行時間制限 : 1ケース 2.000秒 / メモリ制限 : 512 MB / 標準ジャッジ問題
タグ : / 解いたユーザー数 76
作問者 : しらっ亭 / テスター : uwi
6 ProblemId : 1447 / 出題時の順位表 / 自分の提出
問題文最終更新日: 2016-12-26 00:19:29
この問題は Advent Calendar Contest 2016 の15日目の問題です。

注意

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

問題文

P1,P2,P3 を1文字以上の任意の回文、A を 1 文字以上の任意の文字列とします。

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

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

入力

S
  • 1行目に文字列 S が与えられる
  • 4≤|S|≤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もしくは右上の雲マークをクリックしてアカウントを作成してください。