← 返回题目列表

AtCoder · abc213_f

I. 常见前缀

中文机器翻译题面 查看原题

分数: 500 点

问题陈述

让 相似度 f(X,Y) 两个字符串之间 X 和 Y 是它们的最长公共前缀的长度。
例如,之间的相似度 abc 和 axbc is 1,以及之间的相似性 aaa 和 aaaa is 3.

给你一个字符串 S 长度 N。让 S_i 是后缀 S 开头 i- 第一个字符 S。对于每个 k=1,\ldots,N,查找 f(S_k,S_1)+f(S_k,S_2)+\ldots+f(S_k,S_N).

约束

  • 1 \leq N \leq 10^6
  • S 是一个长度为 N 由小写英文字母组成。

输入

输入由标准输入按以下格式给出:

N
S

输出

打印 N 行。

的 i- 第行应包含以下问题的答案 k=i.


示例输入 1

3
abb

示例输出 1

3
3
2

S_1 is abb, S_2 is bb,和 S_3 is 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.

示例输入 2

11
mississippi

示例输出 2

11
16
14
12
13
11
9
7
4
3
4