F - 共同前缀

得分：$500$ 分

问题描述

定义两个字符串 $X$ 和 $Y$ 的相似度 $f(X,Y)$ 为它们最长的公共前缀的长度。
例如，字符串 abc 和 axbc 的相似度为 $1$，字符串 aaa 和 aaaa 的相似度为 $3$。

给定一个长度为 $N$ 的字符串 $S$。对于每个 $k=1,\ldots,N$，求出 $f(S_k,S_1)+f(S_k,S_2)+\ldots+f(S_k,S_N)$。

约束

• $1 \leq N \leq 10^6$
• $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