# Z Algorithm

AC一覧

## Problem Statement問題文

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$ は、$S$ と $S.substr(i)$ の LCP(longest common prefix)

## Constraints制約

• $1 \leq N \leq 500,000$
• Each character of $S$ is lowercase English letters.
• $1 \leq N \leq 500,000$
• $S$ は英小文字からなる。

## Input入力

$S$


## Output出力

$a_0$ $a_1$ $a_2$ ... $a_{N-1}$


## Sampleサンプル

### # 1

abcbcba

7 0 0 0 0 0 1


### # 2

mississippi

11 0 0 0 0 0 0 0 0 0 0


### # 3

ababacaca

9 0 3 0 1 0 1 0 1


### # 4

aaaaa

5 4 3 2 1


Timelimit: 5 secs

Before submitting, please confirm terms and conditions