题目链接

2715. 后缀数组

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

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

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

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

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

特别的，规定 \(Height[1]=0\)。

请你求出这两个数组。

输入格式

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

输出格式

第一行包含 \(n\) 个整数，表示 \(SA\) 数组。

第二行包含 \(n\) 个整数，表示 \(Height\) 数组。

数据范围

\(1≤n≤10^6\)

输入样例：

abababab

输出样例：

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

解题思路

后缀数组，倍增

后缀数组有两个关键的数组：
在后缀形成的数组 \(x[i]\) 中，

• \(SA[i]\) 数组表示数组 \(x\) 中 排名为 \(i\) 的数组下标

• \(Height[i]\) 表示 \(x[i]\) 和 \(x[i-1]\) 的最长公共前缀

\(\color{red}{如何倍增求解 SA 数组？}\)
基于基数排序的思想，设置一个桶 \(c[i]\) 表示值为 \(i\) 的数的数量，先将所有后缀子串按第一个字符排序，基数排序是稳定的，当第一个字符相等时不会改变原后缀子串的顺序，每次排序按长度排序，长度不足后面用字典序最小的字符补齐，例如前一次倍增拍好了长度为 \(k\) 的子串，此时排序长度为 \(2\times k\) 的子串，由于基数排序的稳定性，整体上可以将长度为 \(2\times k\) 的子串先将后 \(k\) 个字符排序，再将前 \(k\) 个字符排序，这样可以保证对于长度为 \(2\times k\) 的子串来说，前 \(k\) 个子串相等，后 \(k\) 个子串也会是排好序的，这样长度为 \(2\times k\) 的子串就排好了序，同时可求解 \(SA\) 数组

• 时间复杂度：\(O(nlogn)\)

\(\color{red}{如何求解 Height 数组？}\)

• 时间复杂度：\(O(n)\)

代码