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