[AdditionalFile6789.zip](file://AdditionalFile6789.zip?type=additional_file)

#6789. ZeTa 的字符串

标签: 传统 | 时间限制: 1000 ms | 内存限制: 512 MiB |

题目描述

$\zeta$ 在论文中的一个字符串 $s$ 中，悟出了一个漫长的，复杂的人生命题。

为了让研究的错误率不超过 $5$ 分，他要对每个位置 $i$ 求出在 $i$ 之前的位置 $j$ 的个数，满足：

$$\operatorname{lcs}(s[1\dots j],s[1\dots i])=s[j+1\dots i]$$

其中 $\operatorname{lcs}(s_i,s_j)$ 表示字符串 $s_i,s_j$ 的最长公共后缀。

输入格式

一行一个仅由小写字母组成的字符串 $s$。

输出格式

一行 $|s|$ 个数，第 $i$ 个数表示 $w_i$。

样例1

输入

aabb

输出

0 1 0 1

样例2

输入

cddcddcdc

输出

0 0 1 0 0 2 0 0 1

样例3

输入

abbcbc

输出

0 0 1 0 0 1

样例4

输入

zzttzttzzttztt

输出

0 1 0 1 0 0 2 0 1 0 1 1 0 3

数据范围与提示

对于 $30\%$ 的数据，$|s|\leq 5\times 10^3$。

对于 $60\%$ 的数据，$|s|\leq 5\times 10^4$。

对于 $100\%$ 的数据，$|s|\leq 5\times 10^5$。

保证输入为小写字母组成的字符串。