AT_abc213_f [ABC213F] Common Prefixes

题目描述

对于两个字符串 $X, Y$，它们的相似度 $f(X, Y)$ 定义为从头开始连续相同的字符数。例如，abc 和 axbc 的相似度为 $1$，aaa 和 aaaa 的相似度为 $3$。

给定一个长度为 $N$ 的字符串 $S$。记 $S_i$ 表示从第 $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$ 时问题的答案。

输入输出样例 #1

输入 #1

3
abb

输出 #1

3
3
2

输入输出样例 #2

输入 #2

11
mississippi

输出 #2

11
16
14
12
13
11
9
7
4
3
4

说明/提示

限制条件

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

样例解释 1

$S_1, S_2, S_3$ 分别为 abb、bb、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$

由 ChatGPT 4.1 翻译