枚举回文串

【题目描述】

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

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

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

【输入】

输入一行，包含一个字符串 $S$。

【输出】

输出一行 $2N-1$ 个整数：$L_0$ $L_1$ … $L_{2N-2}$。

【输入样例】

abcbcba

【输出样例】

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

【输入样例2】

mississippi

【输出样例2】

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

【输入样例3】

ababacaca

【输出样例3】

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

【输入样例4】

aaaaa

【输出样例4】

1 2 3 4 5 4 3 2 1

【数据范围】

• $1 \leq N \leq 500000$
• $S$ 的每个字符均为小写英文字母。

【来源】

Library Checker（yosupo06） enumerate_palindromes