U186306 ZeTa的字符串

本题同步于 [$\text{loj}6789$](https://loj.ac/p/6789)。 自从 $\zeta$ 被 $\text{Lefty Dad}$ 吊打后，开始潜心研究英语论文，并在[ $\text{Tough结构}$ ](https://xueshu.baidu.com/usercenter/paper/show?paperid=173b0e602w2b0c00vr0u0at0p7638246&site=xueshu_se) 的研究上取得了重要突破。 为了成功地被级长一把抓下，并在一群耳朵瞎了、眼睛聋了的人中大显神威， 对语法研究颇深的 $\zeta$ 决定再以压顶之势卷土重来。 这次，他不再玩猫爪老鼠的游戏，计划在 $\text{6月4号}\!\text{月}$ 在阳光明媚的新月背面，干一项大工程。

$\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$ 的最长公共后缀。 $\text{ }$ 简明题意：对每个位置 $i$ 求出 $w_i=\Big|\left\{j|j

无

无

对于 $30\%$ 的数据，$|s|\leq 5\times 10^3$ 对于 $60\%$ 的数据，$|s|\leq 5\times 10^4$ 对于 $100\%$ 的数据，$|s|\leq 5\times 10^5$ 保证输入为小写字母组成的字符串。