算法学习:后缀数组

发布于 / 算法学习 / 0 条评论

后缀数组简介

后缀:从字符串某个位置 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_krank_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 的时候就可以结束循环。整个过程如下图所示:

后缀数组

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

基数排序

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

待更新,请记得提醒博主!

转载原创文章请注明,转载自: KONGJUNE » 算法学习:后缀数组
Not Comment Found