問題一覧 > 通常問題

No.464 PPAP

レベル : / AI推定難易度 : 1300 / 実行時間制限 : 1ケース 2.000秒 / メモリ制限 : 512 MB / 標準ジャッジ問題
タグ : (AC するまで非表示) / 解いたユーザー数 80
作問者 : しらっ亭 / テスター : uwi
お気に入りにしたユーザー ProblemId : 1447 / 自分の提出
問題文最終更新日: 2026-06-25 19:43:17
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
10
There 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
5
There 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もしくは右上の雲マークをクリックしてアカウントを作成してください。