No.465 PPPPPPPPPPPPPPPPAPPPPPPPP
問題文最終更新日: 2026-06-26 06:08:12
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.
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
8The 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もしくは右上の雲マークをクリックしてアカウントを作成してください。
しらっ亭