102135: [AtCoder]ABC213 F - Common Prefixes
Memory Limit：256 MB
Time Limit：2 S
Judge Style：Text Compare
Creator：
Submit：0
Solved：0
Description
Score : $500$ points
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
Input
题意翻译
对于两个字符串 $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_Output
得分：500分
部分
部分
问题描述
令两个字符串X和Y之间的相似性$f(X,Y)$为它们最长公共前缀的长度。
例如，abc和axbc之间的相似性为1，aaa和aaaa之间的相似性为3。
给你一个长度为N的字符串S。令$S_i$为以S的第i个字符开始的S的后缀。对于每个k=1,2,...,N，找出$f(S_k,S_1)+f(S_k,S_2)+...+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$是abb，$S_2$是bb，$S_3$是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