统计回文 （Enumerate Palindromes）

题目描述

给定一个长度为 $N$ 的字符串 $S$。

回文子串的中心位置共有 $2N-1$ 个：可能落在某个字符上，也可能落在两个相邻字符的中间。

对于其中第 $i$ 个位置（从 $0$ 开始编号），定义 $L_i$ 为以该位置为中心的最长回文子串的长度（如果不存在这样的回文子串，则 $L_i = 0$）。请计算出数组 $L_0, L_1, \ldots, L_{2N-2}$。

约束条件

• $1 \leq N \leq 5 \times 10^5$
• 字符串 $S$ 的每个字符均为小写英文字母。

输入

$S$

输出

$L_0 \; L_1 \; \ldots \; L_{2N-2}$

样例

abcbcba

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

mississippi

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

ababacaca

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