Common Prefixes

题目描述

令两个字符串 $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

11
mississippi

11
16
14
12
13
11
9
7
4
3
4

提示

$1 \leq N \leq 10^6$ $S$ 是一个长度为 $N$ 的由小写英文字母组成的字符串。$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$.

标签: AtCoder|abc213F

来源

AtCoder|abc213F