3422 . [模板題] Enumerate Palindromes

Submit out of contest
Status
Discussion / Solution
Ranklist
Back to Problems List

TopCoder

Oyster

User's AC Ratio

100.0% (2/2)

Submission's AC Ratio

100.0% (2/2)

Tags

library-checker template

Description

You are given a string $S$ of length $N$.

There are $2N-1$ positions for the center of a palindromic substring of $S$: at the character or at the middle of two adjacent characters.

For the $i$-th of them ($0$-based), define $L_ i$ as the length of the maximum palindrome centered there (or $L_ i = 0$ if such a palindrome does not exist). Calculate the array $L_ 0,L_ 1,\ldots,L_ {2N-2}$.

Input Format

$S$

Output Format

$L_ 0$ $L_ 1$ ... $L_ {2N-2}$

Sample Input 1

abcbcba

Sample Output 1

1 0 1 0 3 0 7 0 3 0 1 0 1

Sample Input 2

mississippi

Sample Output 2

1 0 1 0 1 4 1 0 7 0 1 4 1 0 1 0 1 4 1 0 1

Sample Input 3

ababacaca

Sample Output 3

1 0 3 0 5 0 3 0 1 0 3 0 5 0 3 0 1

Sample Input 4

aaaaa

Sample Output 4

1 2 3 4 5 4 3 2 1

Hints

  • $1 \leq N \leq 5 \times 10^ {5}$
  • Each character of $S$ is a lowercase English letter.

Problem Source

library checker: enumerate_palindromes

Subtasks

No. Testdata Range Score

Testdata and Limits

No. Time Limit (ms) Memory Limit (VSS, KiB) Output Limit (KiB) Subtasks
0 5000 2097152 2097152
1 5000 2097152 2097152
2 5000 2097152 2097152
3 5000 2097152 2097152
4 5000 2097152 2097152
5 5000 2097152 2097152
6 5000 2097152 2097152
7 5000 2097152 2097152
8 5000 2097152 2097152
9 5000 2097152 2097152
10 5000 2097152 2097152
11 5000 2097152 2097152
12 5000 2097152 2097152
13 5000 2097152 2097152
14 5000 2097152 2097152
15 5000 2097152 2097152
16 5000 2097152 2097152
17 5000 2097152 2097152
18 5000 2097152 2097152
19 5000 2097152 2097152
20 5000 2097152 2097152
21 5000 2097152 2097152
22 5000 2097152 2097152
23 5000 2097152 2097152
Submit out of contest
Back to Top