公共前缀

题目描述

定义两个字符串 $X$ 和 $Y$ 的相似度 $f(X,Y)$ 为它们最长公共前缀的长度。

例如,abc 和 axbc 的相似度为 $1$,aaa 和 aaaa 的相似度为 $3$。

给定一个长度为 $N$ 的字符串 $S$。设 $S_i$ 为 $S$ 从第 $i$ 个字符开始的后缀。对于每个 $k=1,\ldots,N$,求 $f(S_k,S_1)+f(S_k,S_2)+\ldots+f(S_k,S_N)$。

输入格式

输入按以下格式从标准输入给出:

$N$
$S$

输出格式

输出 $N$ 行。

第 $i$ 行应输出 $k=i$ 时的答案。

样例

3
abb

3
3
2

$S_1$ 为 abb,$S_2$ 为 bb,$S_3$ 为 b。

对于 $k=1$:$f(S_1,S_1)+f(S_1,S_2)+f(S_1,S_3)=3+0+0=3$。

对于 $k=2$:$f(S_2,S_1)+f(S_2,S_2)+f(S_2,S_3)=0+2+1=3$。

对于 $k=3$:$f(S_3,S_1)+f(S_3,S_2)+f(S_3,S_3)=0+1+1=2$。

11
mississippi

11
16
14
12
13
11
9
7
4
3
4

数据范围

• $1 \le N \le 10^6$
• $S$ 是长度为 $N$ 的由小写英文字母组成的字符串