Suffix Array

AC一覧

Problem Statement問題文

Given a length $N$ string $S$. Calculate the suffix array of $S$, $a_i$.

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_{N-2}$ $a_{N-1}$


Sampleサンプル

# 1

abcbcba

6 0 5 3 1 4 2


# 2

mississippi

10 7 4 1 0 9 8 6 3 5 2


# 3

ababacaca

8 0 2 6 4 1 3 7 5


# 4

aaaaa

4 3 2 1 0


Timelimit: 5 secs

Before submitting, please confirm terms and conditions