课堂内容

后缀数组

后缀数组主要指两个数组 $sa$ 和 $rank$：

• $sa_i$ 表示所有后缀中按字典序大小从小到大排序后排名为 $i$ 的后缀的起始位置。
• $rank_i$ 表示以 $i$ 为起始位置的后缀的排名。

其中这两个数组有如下性质：

可以使用倍增 + 基数排序的方式求解 $sa$ 和 $rank$ 数组，复杂度 $O(n \log n)$。

除此之外，还有一个 $height$ 数组表示 $sa_i$ 和 $sa_{i-1}$ 两个后缀的 LCP (Longest Common Prefix) 的长度。

模版题：Luogu-P10469 后缀数组 提交记录：Link

例题

Luogu-P3809 后缀排序

题目大意

给定一个长度为 $n$ 的仅由小写字母组成的字符串，将其所有后缀按字典序从小到大排序后，求排名为 $i$ 的后缀的起始位置。

思路

就是后缀数组的简单应用，求出 $sa$ 数组后输出即可。注意下标的问题。

提交记录：Link