字符串

• 前缀树/字典树
• 后缀树
• 后缀数组

前缀树

字典树

后缀数组

在字符串处理中，后缀树和后缀数组（Suffix Array）都是非常有力的工具。

后缀数组是后缀树的一个非常精巧的替代品，比后缀树容易实现，可以实现后缀树的很多功能，时间复杂度也不逊色，比后缀树所占用的空间也小很多。在算法竞赛中，后缀数组比后缀树更为实用。

概念

① 后缀。

后缀指从某个位置开始到字符串末尾的一个特殊子串。字符串s 从第i 个字符开始的后缀被表示为Suffix(i)，也可以称之为下标为i 的后缀。字符串s =“aabaaaab”，其所有后缀如下：

② 后缀数组。

将所有后缀都从小到大排序之后，将排好序的后缀的下标i 放入数组中，该数组就叫作后缀数组。将上面的所有后缀都按字典序排序之后，取其下标i ，即可得到后缀数组：

③ 排名数组。

排名数组指下标为i 的后缀排序后的名次，例如在上面例子中排序后的下标和名次。若rank[i]=num，则下标为i 的后缀排序后的名次为num：

构建

构建后缀数组有两种方法：

• DC3算法
• 倍增算法

DC3算法的时间复杂度为O (n )，倍增算法的时间复杂度为O (n logn )。一般n >10^6时，DC3算法比倍增算法运行速度快，但是DC3算法的常数和代码量较大，因此倍增算法比较常用。

倍增算法，对字符串从每个下标开始的长度为$2^k$ 的子串进行排序，得到排名。k 从0开始，每次都增加1，相当于长度增加了1倍。当2^k ≥n 时，从每个下标开始的长度为2^k 的子串都相当于所有后缀。每次子串排序都利用上一次子串的排名得到。