loj#P6789. ZeTa 的字符串

ZeTa 的字符串

题目描述

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

为了让研究的错误率不超过 55 分,他要对每个位置 ii 求出在 ii 之前的位置 jj 的个数,满足:

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

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

输入格式

一行一个仅由小写字母组成的字符串 ss

输出格式

一行 s|s| 个数,第 ii 个数表示 wiw_i

aabb
0 1 0 1
cddcddcdc
0 0 1 0 0 2 0 0 1
abbcbc
0 0 1 0 0 1
zzttzttzzttztt
0 1 0 1 0 0 2 0 1 0 1 1 0 3

数据范围与提示

对于 30%30\% 的数据,s5×103|s|\leq 5\times 10^3

对于 60%60\% 的数据,s5×104|s|\leq 5\times 10^4

对于 100%100\% 的数据,s5×105|s|\leq 5\times 10^5

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