9033: [yosupo] String - Enumerate Palindromes
[Creator : ]
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}$.
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
$S$
Output
$L_0$ $L_1$ ... $L_{2N-2}$
Constraints
$1 \leq N \leq 5 \times 10^5$
Each character of $S$ is a lowercase English letter.
Each character of $S$ is a lowercase English letter.
Sample 1 Input
abcbcba
Sample 1 Output
1 0 1 0 3 0 7 0 3 0 1 0 1
Sample 2 Input
mississippi
Sample 2 Output
1 0 1 0 1 4 1 0 7 0 1 4 1 0 1 0 1 4 1 0 1
Sample 3 Input
ababacaca
Sample 3 Output
1 0 3 0 5 0 3 0 1 0 3 0 5 0 3 0 1
aaaaa
1 2 3 4 5 4 3 2 1
HINT
相同题目：yosupo。