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)$.

長さ $N$ の文字列 $S$ が与えられます。以下の条件を満たす配列 $a_0, a_1, ..., a_{N - 1}$ を出力してください。

  • $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

Forum


Timelimit: 5 secs

Before submitting, please confirm terms and conditions