問題一覧 > 通常問題

No.465 PPPPPPPPPPPPPPPPAPPPPPPPP

レベル : / AI推定難易度 : 2900 / 実行時間制限 : 1ケース 2.000秒 / メモリ制限 : 512 MB / 標準ジャッジ問題
タグ : (AC するまで非表示) / 解いたユーザー数 15
作問者 : uwi / テスター : しらっ亭
お気に入りにしたユーザー ProblemId : 1467 / 自分の提出
問題文最終更新日: 2026-06-26 06:08:12
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.

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 first line contains the string $S$.
  • $4 \le |S| \le 500000$
  • $S$ consists only of lowercase English letters.

Output

Print the answer as an integer on one line.

Print a newline at the end.

Sample

Sample 1
Input
testsetlevelisminim
Output
8
The following $8$ tuples satisfy the condition.
  • (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)
Sample 2
Input
xxoxxxxoxxoxxoxxxxoxxxxoxxxxoxxoxxoxxxxoxx
Output
92
Sample 3
Input
ppppppppppppppppapppppppp
Output
1009

提出するには、Twitter 、GitHub、 Googleもしくは右上の雲マークをクリックしてアカウントを作成してください。