分数: 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