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 \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 翻译