No.464 PPAP
問題文最終更新日: 2026-06-25 19:43:17
English (AI translation)
This statement was translated by AI (claude-opus-5-5, effort medium) and may contain errors or differ in nuance from the original. The original statement takes precedence.
Back to the original
Advent Calendar Contest 2016
(順位表)
の他の問題:
This problem is the problem for day 15 of Advent Calendar Contest 2016.
Note
The intended solution has been confirmed to get AC in C++14, PyPy3, PyPy2, and Java8 (code by a tester), but it gets TLE in plain Python.
Please be aware of this.
Problem Statement
Let $P_1, P_2, P_3$ be arbitrary palindromes of at least $1$ character, and let $A$ be an arbitrary string of at least $1$ character.
A string $S$ is given as input.
Let $PPAP$ be the string obtained by concatenating $P_1, P_2, A, P_3$ in this order. How many tuples $(P_1, P_2, A, P_3)$ satisfy $PPAP = S$?
Input
S
- The string $S$ is given on the first line.
- $4 \le |S| \le 5000$
- $S$ consists only of lowercase English letters.
Output
Output the answer as an integer on one line.
Print a newline at the end.
Sample
Sample 1
Input
abcd
Output
1
There is $1$ way: (a, b, c, d).
Sample 2
Input
ababababa
Output
10There are the following $10$ ways.
(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)
Sample 3
Input
penpineappleapplepen
Output
1
There is $1$ way: (p, e, npineappleapplepe, n).
Sample 4
Input
mississippi
Output
5There are the following $5$ ways.
(m, i, ssiss, ippi)(m, i, ssissipp, i)(m, issi, ss, ippi)(m, issi, ssipp, i)(m, ississi, pp, i)
提出するには、Twitter 、GitHub、 Googleもしくは右上の雲マークをクリックしてアカウントを作成してください。
しらっ亭