9032: [yosupo] String - Z Algorithm
[Creator : ]
Description
Given a length $N$ string $S$. Calculate array $a_0, a_1, ..., a_{N - 1}$ as follows:
- $a_i$ is the LCP(longest common prefix) of $S$ and $S.substr(i)$.
- $a_i$ is the LCP(longest common prefix) of $S$ and $S.substr(i)$.
Input
$S$
Output
$a_0$ $a_1$ $a_2$ ... $a_{N-1}$
Constraints
$1 \leq N \leq 5 \times 10^5$
Each character of $S$ is lowercase English letters.
Each character of $S$ is lowercase English letters.
Sample 1 Input
abcbcba
Sample 1 Output
7 0 0 0 0 0 1
Sample 2 Input
mississippi
Sample 2 Output
11 0 0 0 0 0 0 0 0 0 0
Sample 3 Input
ababacaca
Sample 3 Output
9 0 3 0 1 0 1 0 1
aaaaa
5 4 3 2 1
HINT
相同题目：yosupo。