后缀数组


机房的大佬们学完了后缀数组,躲在墙角打树状数组模板的蒟蒻我瑟瑟发抖

说起后缀数组,暑假的时候有学长讲过一遍字符串的一些算法,讲过了后缀数组,但是这样只有一个印象,不能理解也不会实现。

但是现在,在善良的学长Tyw_ei的帮助下,我总算是理解了后缀数组。
他的博客: Link

首先

为什么要学后缀数组?

虽然我曾经也在博客中说过,字符串的题简单的$hash$,难的就不会。所以学了也没用。但是,学了总比没学强啊…..加上代码也不长,万一考个毒瘤字符串刚好会做了呢…..

其次,虽然后缀自动机($SAM$)的复杂度是$O(n)$的,后缀数组的复杂度是$O(nlogn)$的,后缀数组还是有着一些后缀自动机没有的功能,于是要学。

基数排序

后缀数组基于对后缀进行排序,需要利用到更高效的排序方式。
没错,就是基数排序
所谓基数排序,在我的理解上也就是多次的桶排

日常生活中,比较两个数的大小,我们先回去看长度,如果相等,则一位一位去比较。
基数排序则类似,不同的是,我们按照尾部对其,前面长度不足的话就补$0$,对每一位进行排序。

为什么从尾部(低位)开始? (LSD)

显然,如果从低位可以,从高位开始也是一定可以的。(MSD)
$LSD$ : 数$a$和$b$如果第$i$位相同,则比较第$i + 1$位,此时如果已经对第$i + 1$位排好序了,那么对于第$i$位相等时的情况就不需要去比较,写起来也很方便。
$MSD$ : 实现方法相同,如果匹配完第一个数字,把这一位相同的分为一段,用一个容器维护,保证每一段之间的单调性,数字只在段内移动,最后段数剩下一段时排序完成。这样显然是可行的,但是写起来比较复杂,在空间上也会有许多开销。所以一般从第一位开始。

排序的方式就是把每一个数这一位的数字插入桶中,比较,给每个数找一个排完序的序号。
这里$tax$数组是桶,先把数字放到桶里面


然后倒出来,给它一个排序的序号,如果当前关键字相同则按照第二关键字顺序进行排序


a[i] = b[i]的原因是更新第二关键字,以便下次排序。

总体代码在下面。

后缀数组

因为博主十分的弱,不会$DC3$,所以只学了好懂的倍增。
注:博客参考 Link1Link2

几个定义

还是这个经典的图,把一个字符串的后缀进行排序。
SuffixArray

下面是几个数组的含义
$str$ : 原串
$Rank[i]$: 表示从原串开始的第$Rank[i]$的后缀排名为$i$。
$SA[i]$ : 表示排名为$i$的串是从第$SA[i]$个后缀。
$Height[i]$ : 表示第$Rank[i]$和$Rank[i]-1$后缀的最长公共前缀。
注意 :$SA$与$Rank$为互逆数组。

思路

简单来说,倍增算法分以下四步

  1. 对长度为 $2^0=1$ 的字符串,也就是所有单字母排序。
  2. 用长度为 $2^0=1$ 的字符串,对长度为 $2^1=2$的字符串进行双关键字排序。考虑到时间效率,我们一般用基数排序。
  3. 用长度为 $2^{k-1}$ 的字符串,对长度为 $2^k$ 的字符串进行双关键字排序。
  4. 直到 $2^k ≥ n$,或者名次数组 $Rank$ 已经从 $1$ 排到 $n$,得到最终的后缀数组。

以字符串 “aabaaaab” 为例, 整个过程如图所示。 其中$x$、 $y$ 是表示长度为 $2^k$ 的字符串的两个关键字。

总体理解:第$i$次把后面$2^{i – 1}$的子串合并起来,没有第二关键字的则补$0$,利用上次的答案,对$2^i$进行基数排序,得到这次的结果。这一个过程是倍增的。

代码
代码中$m$的初始值是第一次排序时用到的,也就是最大的值域.
$p$是当前已经被排序出了$p$个块,如果$p=n$的时候就是排序完成了,每次在排序完成后对$SA$数组进行比较(如果两个关键字相等则为相等),更新$Rank$,(类似离散化里面去重的比较)。


基排部分


$cmp$部分

Height数组

回顾一下定义:$Height[i]$ : 表示第$Rank[i]$和$Rank[i]-1$后缀的最长公共前缀。
那么直接把$Rank[i]$和$Rank[i]-1$进行暴力排序显然是不可取的。复杂度$O(n^2)$

如何高效求解$Height$?

一个性质:
$$Height[Rank[i]] ≥ Height[Rank[i] – 1]-1$$
一般定义$H[i]$为$Height[Rank[i]]$,有
$$H[i] ≥ H[i-1]-1$$
证明
设$suffix(k)$是排在$suffix(i-1)$前一名的后缀,它们的最长公共前缀是$H[i-1]$。
那么$suffix(k+1)$将排在$suffix(i)$的前面(这里要求$H[i-1]>1$,如果$H[i-1]≤1$,原式显然成立)并且$suffix(k+1)$和$suffix(i)$的最长公共前缀是$H[i-1]-1$)

代码:

时间复杂度

显然是$O(nlogn)的$,最外层是$logn$的,里面因为是基数排序,计算$Height$,都为$O(n)$。

模板

基数排序

后缀数组

练习题

Luogu模板

题意:输出SA数组
题解:输出SA数组
代码:

最长可重叠重复K次子串问题

后缀数组一·重复旋律

Link
题意:求出现次数至少为$K$次的旋律最长是多少
题解:即要求$Height$数组中连续$K$个东西最小值 的最大值。$RMQ$或者单调队列解决。复杂度$O(nlogn)$

最长不可重叠重复子串问题

后缀数组二·重复旋律

Link
题意:求出现次数至少为$2$次的旋律最长是多少,要求不能重复
题解:和上一个题的区别是要求不能重复,那么利用上次的方法可能显得不好解决,把问题转换为判定性问题则可能更好。那么二分答案,问题就是如何判断了。我们可以对于$Height$数组进行划分,把连续的$Height$大于$k$的划分为一组。在每一组中,如果最大的$SA$减去最小的$SA$大于等于$K$那么是可行的。注意数的值域是$1000$,之前写的$255$,RE了两发。

PS:
题目中仅仅是出现两次,那么出现多次怎么处理呢?
我们可以对于分出的块里面的$SA$排序,看看是否有$k$个子串是不重合的。这样的复杂度是$O(nlog^2n)$,那么只要基排就行了,复杂度仍然为$O(nlogn)$

代码:

POJ1743

Link
题意:
求重复出现的子串满足如下性质:
1. 求出的长度不能小于$5$。
2. 如果串$a$是$b$整体加$x$得到的被视为相等
3. 不能重叠
题解:显然是最长不可重叠重复子串问题,那么对于要求$2$就需要特殊考虑,其实只需要记录差值就好了,无论加多少,元素之间的相对差是不变的。1 2 33 4 5 转换过来都是1 1 ,所以对原串进行处理成差的性质,答案为最长不可重叠重复子串加1。
代码:

最长公共子串问题

后缀数组三·重复旋律

Link
题意:求两个串最长公共子串,要求子串是连续的
题解:把两个串拼起来,在中间加上一个’#’或是小于’a’的其他字符,然后跑一遍后缀数组,求$Height$。但此时的最大$Height$值不是答案,因为可能在单独串中匹配。所以统计答案的时候判断一下$SA$数组是否在同一个串里就行了,如果在则不能更新答案。

PS:对于多个串的答案,需要二分。对于二分出的$k$值分组(这样的方法用的很多),对于分出的大于$k$的组,判断这一组里是否包含了所有的串(即$SA$值属于每一个串)。

代码:

Leave a Reply

Your email address will not be published. Required fields are marked *