题目描述

$2$ つの文字列 $X,Y$ に対して、その類似度 $f(X,Y)$ を、$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$ の問題の答えを出力せよ。

题目大意

对于两个字符串 $X,Y$，定义 $f(X,Y)$ 为 $X$ 和 $Y$ 的最长公共前缀长度。现给定一个长为 $n$ 的字符串 $S$，定义 $S_i$ 表示 $S$ 的从第 $i$ 个字符开始的后缀（包含第 $i$ 个字符），你需要对于所有的 $1\le k\le n$ 求出 $\sum\limits_{i=1}^nf(S_k,S_i)$。

Translated by _Ponder_

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$ の文字列

Sample Explanation 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$