Score : $500$ points

问题描述

令两个字符串 $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)$ 的值。

以上为通义千问 qwen-max 翻译，仅供参考。

Problem Statement

Let the similarity $f(X,Y)$ between two strings $X$ and $Y$ be the length of their longest common prefix.
For example, the similarity between abc and axbc is $1$, and the similarity between aaa and aaaa is $3$.

You are given a string $S$ of length $N$. Let $S_i$ be the suffix of $S$ beginning with the $i$-th character of $S$. For each $k=1,\ldots,N$, find $f(S_k,S_1)+f(S_k,S_2)+\ldots+f(S_k,S_N)$.

Constraints

• $1 \leq N \leq 10^6$
• $S$ is a string of length $N$ consisting of lowercase English letters.

Input

Input is given from Standard Input in the following format:

$N$

$S$

Output

Print $N$ lines.

The $i$-th line should contain the answer for $k=i$.

Sample Input 1

3
abb

Sample Output 1

3
3
2

$S_1$ is abb, $S_2$ is bb, and $S_3$ is b.

• For $k=1$: $f(S_1,S_1)+f(S_1,S_2)+f(S_1,S_3)=3+0+0=3$.
• For $k=2$: $f(S_2,S_1)+f(S_2,S_2)+f(S_2,S_3)=0+2+1=3$.
• For $k=3$: $f(S_3,S_1)+f(S_3,S_2)+f(S_3,S_3)=0+1+1=2$.

Sample Input 2

11
mississippi

Sample Output 2

11
16
14
12
13
11
9
7
4
3
4

update @ 2024/3/10 09:30:07