算法学习:后缀数组

算法学习:后缀数组

学习自:

后缀数组简介

后缀:从字符串某个位置 $i$ 到字符串末尾的子串,我们定义以字符串 $str$ 的第 $i$ 位为第一个元素的后缀为suff[i]。(后缀的英文:suffix

后缀数组:把字符串 $str$ 的每一个后缀按照字典序排序后所形成的数组。

后缀数组的实现

变量定义

  • suff[]数组,用来记录从第 $i$ 位开始的后缀
  • sa[]数组(suffix array),存储的是字典第 $i$ 小的后缀的下标。比如sa[0] = 8代表的是suff[]数组中第 $8$ 位后缀在字典序中最小。而suff(sa[0])才真正存储这最小的那个后缀的内容。
  • rank[]数组,与sa[]相反,存储的是下标为 $i$ 的后缀为第几小。一定存在关系 $\text{rank}[\text{sa}[i]] = i$。

倍增算法

问题在于我们怎么给这个后缀数组排序,如果强硬 sort 的话,sort 算法复杂度本来就有 $O(n\log_2n)$ 字符串排序还不用于一般数字的排序,每个字符串对比还有 $O(n)$ 复杂度。也就是说用 sort 的话,复杂度会达到 $O(n^2\log_2n)$。这就很伤不是么,所以我们要想出来一个复杂度更低的算法。

我们知道,两个字符串的比较,如果前半部分相同则比较结果取决于后半部分的比较结果,否则只需要看前半部分的比较结果。基于这个事实,我们考虑以下方法:

对于字符串 $str$,定义k-前缀为:

$$
str_k=\begin{cases}
str[0\dots k - 1] = str.\mathrm{substr}(0, k) & (k\leq str.\mathrm{length}()) \\
str & (k > str.\mathrm{length}())
\end{cases}
$$
然后类似的,我们定义出基于k-前缀意义下的sa[]数组和rank[]数组,在这里我们记作 $sa_k$ 与 $rank_k$ 数组。其中 $sa_k$ 为k-前缀意义下的后缀数组,$rank_k$ 为k-前缀意义下的名次数组。则有以下计算方式:

  • 容易求出 $rank_1$ 的值与 $sa_1$ 的值,只需要进行 sort 对第一个字母排序就可以了。

  • 得到了 $rank_k$,则定义二元组 $(rank_k[i],rank_k[i + k])$,按照“如果 $rank_k[i]$ 相同则比较$rank_k[i +k]$,否则则比较 $rank_k[i]$ ”的方法来进行sort,即可求出 $sa_{2k}$。

  • 求出了 $sa_k$ 则可以很快求出 $rank_k$,有以下关系:
    $$
    rank_k[i] = \begin{cases}
    rank_k[i - 1] & suff[sa[i]]_k = suff[sa[i - 1]]_k \\
    rank_k[i - 1] + 1 & suff[sa[i]] _ k \neq suff[sa[i - 1]]_k
    \end{cases}
    $$

这样的话我们求解的顺序就是:
$$
sa_1 \ \& \ rank_1 \rightarrow sa_2 \rightarrow rank_2 \rightarrow sa_4 \rightarrow rank_4 \rightarrow \cdots \rightarrow sa_n \rightarrow rank_n
$$
当不再出现并列的 $rank$ 的时候就可以结束循环。整个过程如下图所示:

1564227558972

每一次排序需要进行 $n\log_2n$ 次比较,每一次比较需要 $O(1)$ 复杂度,总共进行 $\log_2n$ 次比较,因此总时间复杂度为$O(n\log_2^2n)$。

基数排序

这一部分我们要试图探索比 $O(n\log _2^2n)$ 更优的排序算法。

评论

Your browser is out-of-date!

Update your browser to view this website correctly. Update my browser now

×