后缀数组基本知识

· · 个人记录

后缀数组

后缀数组是三个数组， 分别名为 sa、rank、 height， 它们包含的信息都是同一个字符串的。

sa数组

sa 数组的定义 一个串 S 的后缀 S[l:|S|] 用 l 表示， 将 S 的所有后缀排序， sa 数组存储的就是有序的后缀编号 l。

暴力求 sa 如果用 C++ 带的 sort 函数来后缀排序的话， 时间复杂度是 O(n^2 \log_2 n) 的， 因为两个字符串的比较的时间复杂度是 O(n) 的。

快速排序与基数排序 对于用 k 个关键字排序 n 个数， 快速排序能做到 O(kn \log_2 n), 基数排序能做到 O(kn)。 下面简要分析一下它们的排序过程。

快速排序： 都知道 sort 函数提供了 cmp 函数的接口。 基数排序： 基数排序是将多个关键字分开， 从低优先级的关键字到高优先级的关键字依次排一遍（稳定排序）。

倍增法 倍增法的低复杂度依托于后缀排序这个问题的特殊性质。 有了 S[i\in[1,n], i+2^{k-1}-1] 的排序结果， 就可以得到 S[i\in[1,n], i+2^k-1] 的排序结果。 每一次倍增的过程中都要用到一次二关键字排序， 用基数排序就可以将一次倍增做到 O(n)。 倍增法的总复杂度为 O(n\log_2 n)。

LCP 与 sa数组

设 lcp(i,j) 表示 LCP(sa_i, sa_j)

+

证明：对于两个串 $A$、 $B$， 它们都有 $n$ 个关键字（不足补空）， $A_i$ 即 $A$ 的第 $i$ 关键字， $LCP(A,B) = k$ 即 $A$、 $B$ 的前 $k$ 个关键字都相等， 第 $k+1$ 关键字不同。 由于排序的性质， 对于一个串 $S$ 和与其相对位置相同的一些串来说， 排序后第一关键字与 $S$ 相同的那些串一定比第一关键字与 $S$ 不同的那些串近 （因为第一关键字相同的在整个数组中一定是连续的）， 这也就说明了与 $S$ 的最长公共前缀为 $0$ 的串总是离 $S$ 较与 $S$ 的最长公共前缀为 $\ge 1$ 的串远。 在与 $S$ 的 $LCP$ 大于等于 $1$ 的那个连续段中， 第二关键字就是第一关键字， 用归纳法就可以发现这个 $\Delta \delta$ 性质。 **+** 有了这个 $\Delta \delta$ 性质， 可以证明一个定理： $$lcp(i,j) = min\{ lcp(i,k), lcp(k,j) \} \;\;\; (i\le k \le j)$$ 证明： 首先 $lcp(i,k) \ge min\{ lcp(i,k), lcp(k,j) \}$ 且 $lcp(k,j) \ge min\{ lcp(i,k), lcp(k,j) \}$， 由此推出 i、j 前 $min\{ lcp(i,k), lcp(k,j) \}$ 个字符相等， 即 $lcp(i,j) \ge min\{ lcp(i,k), lcp(k,j) \}$。 由 $\Delta \delta$ 性质， $lcp(i,j) \le lcp(i,k)$ 且 $lcp(j,i) \le lcp(j,k)$， 即 $lcp(i,j) \le min\{ lcp(i,k), lcp(k,j) \}$。 综上， $lcp(i,j) = min\{ lcp(i,k), lcp(k,j) \}$。 **需要注意的是， 这个定理也适用于任意字符串排序的结果数组， 而不仅仅是后缀排序的结果数组** 这个定理有一个应用： $$lcp(i,j) = \min_{k=i+1}^j\{lcp(k,k-1)\}$$ 证明： 将 $lcp(i,j)$ 按照定理展开， 最终就可以得到这个式子。（至于展开的过程中 $k$ 怎么选， 当然是随便选啦owo） --- ###**rk 数组** rk 数组是 sa 数组的反函数， 意即 $sa[rk[i]] = i$。 --- ###**height 数组** 定义 $$height_i = LCP(sa_i, sa_{i-1})$$ 意即排名为 i 的后缀与排名为 i-1 的后缀的 LCP。 又有 $$h_i = height_{rank_i} = LCP(i, sa_{rank_i - 1})$$ 意即后缀 i 与排在它前面一个的后缀的 LCP。 这里有一个定理： $$\forall 1<i \le n, \; h_i \ge h_{i-1} - 1$$ 证明： 如果 $h_{i-1} \le 1$， 那么显然成立。 如果 $h_{i-1} > 1$， 那么将 $i-1$ 和 $sa_{rank_{i-1} - 1}$ 都去掉第一个字符， 得到 $i$ 和 $sa_{rank_{i-1} - 1}+1$， 它们的 $LCP$ 就是 $h_{i-1}-1$; 由字典序的知识可知 $sa_{rank_{i-1} - 1}+1$ 依然排在 $i$ 前面， 再由 $i$ 前面离 $i$ 最近的是 $sa_{rank_i - 1}$ 和 $\Delta\delta$ 性质， 定理就得证了。 有了这个定理， 就可以 $O(n)$ 求出 $h$ 数组， 进而 $height$ 数组也就可以求出了。 以上就是后缀数组的基本知识了。