后缀数组

【题目描述】

给定一个长度为 $N$ 的字符串 $S$。求 $S$ 的后缀数组 $a_i$。

【输入】

$S$

【输出】

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

【输入样例】

abcbcba

【输出样例】

6 0 5 3 1 4 2

【输入样例2】

mississippi

【输出样例2】

10 7 4 1 0 9 8 6 3 5 2

【输入样例3】

ababacaca

【输出样例3】

8 0 2 6 4 1 3 7 5

【输入样例4】

aaaaa

【输出样例4】

4 3 2 1 0

【数据范围】

• $1 \leq N \leq 500000$
• $S$ 的每个字符均为小写英文字母。

【来源】

Library Checker（yosupo06） suffixarray