2715

2715. 后缀数组

题目

给定一个长度为 $n$ 的字符串，只包含大小写英文字母和数字。

将字符串中的 $n$ 个字符的位置编号按顺序设为 $1 \sim n$。

并将该字符串的 $n$ 个 非空后缀 用其起始字符在字符串中的位置编号表示。

现在要对这 $n$ 个非空后缀进行字典序排序，并给定两个数组 $SA$ 和 $Height$。

排序完成后，用 $SA[i]$ 来记录排名为 $i$ 的非空后缀的编号，用 $Height[i]$ 来记录排名为 $i$ 的非空后缀与排名为 $i-1$ 的非空后缀的最长公共前缀的长度（$1 \le i \le n$）。

特别的，规定 $Height[1] = 0$。

请你求出这两个数组。

输入格式

共一行，包含一个长度为 $n$ 的仅包含大小写英文字母或数字的字符串。

输出格式

第一行包含 $n$ 个整数，表示 $SA$ 数组。

第二行包含 $n$ 个整数，表示 $Height$ 数组。

数据范围

$1 \le n \le 10^6$

输入样例：

abababab

输出样例：

7 5 3 1 8 6 4 2
0 2 4 6 0 1 3 5

题解