学习笔记 后缀数组

发表于 | 更新于 | 分类于 | 阅读次数：

后缀数组（SA）是处理字符串的有力工具。它较后缀自动机更易理解，较后缀树更容易实现，并且SA也完全不比它们中的任何一者逊色。

本文将介绍后缀数组的$n \log n$倍增求法以及它的性质与简单应用。

一些定义

在详述算法之前，我们得先对一些定义有所了解。

子串

$s[l..r](l \le r)$表示字符串$S$的$l$到$r$，即$s[l], s[l + 1]…s[r - 1], s[r]$构成的字符串。

后缀

$\text{Suffix} (i)$表示字符串$S$从第$i$个字符开始直到末尾的字符串，即$s[i, len]$这个子串。

字符串大小

即字符串的字典序大小。对于两个字符串$s$和$t$，从头开始依次比较每一个字符，若$s[i] = t[i]$则比较下一个字符，否则若$s[i] < t[i]$则$s < t$；若$s[i] > t[i]$则$s > t$。若其中一个字符串已经到尾了仍无结果，那么若$len(s) < len(t)$则$s < t$；若$len(s) > len(t)$则$s > t$；若$len(s) = len(t)$则$s = t$。

后缀数组

一维数组$SA$存储了$1 \sim n$的某个排列，保证$\forall i (1 \le i \lt n), \text{Suffix} (SA[i]) < \text{Suffix} (SA[i + 1])$，即$S$的所有后缀从小到大排序后第$i$名起始位置。

名次数组

一维数组$Rank$同样存储了$1 \sim n$的某个排列，它表示$\text{Suffix} (i)$的排名。$Rank$数组与$SA$数组是互逆的，即$Rank[SA[i]] = i,\ SA[Rank[i]] = i$。

SA的倍增求法

现在开始详细地讲述倍增算法。

思想

暴力算法，是将所有后缀存下来，进行快排，复杂度$\mathcal {O} (n ^ 2 \log n)$

这样当然不行，我们要进行优化

倍增算法的核心思想是：假设我们已经求出所有后缀以前$2 ^ k$个字符排序后的结果，那么我们可以根据已求出的长为$2 ^ k$的后缀排名，求出长为$2 ^ {k + 1}$的后缀排名，在若干次这样的操作后将$SA$数组完整地求出。

至于排序的过程，我们可以将长度为$2 ^ {k + 1}$的字符串拆分成一前一后两个长度均为$2 ^ k$的字符串，以前半部分为第一关键字，后半部分为第二关键字，进行基数排序，当然这里也可换用快排，这样总复杂度就会变成$\mathcal {O}(n \log ^ 2n)$

下面的图片非常形象地展示了这一过程

img

详解

先展示一部分代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
void Build_SA() {
    int Size = 300;
    for (int i = 1; i <= n; ++i) Rank[i] = str[i] - '0' + 1, tp[i] = i;
    Radix_Sort(Size);
    for (int len = 1, p = 0; p < n; Size = p, len <<= 1) {
        p = 0;
        for (int i = n - len + 1; i <= n; ++i) tp[++p] = i;
        for (int i = 1; i <= n; ++i) if (SA[i] > len) tp[++p] = SA[i] - len;
        Radix_Sort(Size);
        std::swap(Rank, tp);
        Rank[SA[1]] = p = 1;
        for (int i = 2; i <= n; ++i) Rank[SA[i]] = tp[SA[i]] == tp[SA[i - 1]] && tp[SA[i] + len] == tp[SA[i - 1] + len] ? p : ++p;
    }
}

在一开始，我们钦定每个后缀的$rank$值（第一关键字）为其首字符值，$tp$值（第二关键字）为其位置（规定字典序一样的先出现的排在前面），进行基数排序。$Size$为字符集（亦即排序时的数值范围）大小。此时我们已将长为$2 ^ 0 = 1$的后缀排序完毕。

1
for (int len = 1, p = 0; p < n; Size = p, len <<= 1) {

接下来我们开始倍增。$len$为其上一次排序时的长度（也就是这次的一半），$p$为不同的$SA$值的数量，当$p = n$时，所有的后缀排名都不相同，我们已经得出了$SA$数组，便可退出循环。

1
2
3
p = 0;
for (int i = n - len + 1; i <= n; ++i) tp[++p] = i;
for (int i = 1; i <= n; ++i) if (SA[i] > len) tp[++p] = SA[i] - len;

每次循环开始时，我们要先求出$tp$数组，代表长度为$2len$的后缀中第二关键字排名为$i$的位置，在基数排序中有用到。注意，最后$len$个后缀此时已经不需拼接上后缀，因此它们的第二关键字大小为$0$，应排在最前面。而对于长度大于$len$的后缀，它们的第二关键字排名应由上一轮的$SA$数组得到，因此我们从小到大枚举，将$SA$数组中可作为第二关键字的值减去$len$（因为$SA$数组和$tp$数组存的都是位置，减去则是因为这是第二关键字）存入$tp$。

1
Radix_Sort(Size);

然后是基数排序，后面再说。

1
2
3
std::swap(Rank, tp);
Rank[SA[1]] = p = 1;
for (int i = 2; i <= n; ++i) Rank[SA[i]] = tp[SA[i]] == tp[SA[i - 1]] && tp[SA[i] + len] == tp[SA[i - 1] + len] ? p : ++p;

排完序后我们要由新的$SA$数组得到$Rank$数组。因此我们再次从小到大枚举，并进行比较：如果某个后缀与其前一名后缀的前半段和后半段在上一轮的排名都一样，那我们则记他们拥有一样的$Rank$值，并以此更新$p$值。

基数排序

1
2
3
4
5
6
void Radix_Sort(int S) {
	for (int i = 1; i <= S; ++i) tax[i] = 0;
	for (int i = 1; i <= n; ++i) tax[Rank[i]]++;
	for (int i = 1; i <= S; ++i) tax[i] += tax[i - 1];
	for (int i = n; i >= 1; --i) SA[tax[Rank[tp[i]]]--] = tp[i];
}

比较绕。在前一轮我们已经对第二关键字进行了排序，并存到了$tp$数组中，现在我们只需以此为基础考虑第一关键字（$Rank$）即可。回顾一下此时三个数组的意义

  • $SA[i]$：长度为$2len$时排名为$i$的后缀所在位置
  • $Rank[i]$：长度为$len$时第$i$个后缀的排名，即长度为$2len$时第$i$个后缀第一关键字的排名
  • $tp[i]$：长度为$2len$时第二关键字排名为$i$的后缀所在位置

我们先用一个桶（$tax$数组）统计第一关键字出现次数，并对其做前缀和，得到“第一关键字比我小”的后缀有多少个

然后我们从大到小枚举第二关键字（$tp$），由$Rank[tp[i]]$定位到其第一关键字的桶中位置，此时$tax[Rank[tp[i]]]$就表示当第一关键字相同时，第二关键字更大的后缀的排名，以此更新$SA$数组的值。

这是后缀数组构建中最难理解的一部分，但同时也是其精华所在。

SA构建部分代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
void Radix_Sort(int S) {
	for (int i = 1; i <= S; ++i) tax[i] = 0;
	for (int i = 1; i <= n; ++i) tax[Rank[i]]++;
	for (int i = 1; i <= S; ++i) tax[i] += tax[i - 1];
	for (int i = n; i >= 1; --i) SA[tax[Rank[tp[i]]]--] = tp[i];
}
void Build_SA() {
	int Size = 300;
	for (int i = 1; i <= n; ++i) Rank[i] = str[i] - '0' + 1, tp[i] = i;
	Radix_Sort(Size);
	for (int len = 1, p = 0; p < n; Size = p, len <<= 1) {
        p = 0;
        for (int i = n - len + 1; i <= n; ++i) tp[++p] = i;
        for (int i = 1; i <= n; ++i) if (SA[i] > len) tp[++p] = SA[i] - len;
        Radix_Sort(Size);
        std::swap(Rank, tp);
        Rank[SA[1]] = p = 1;
        for (int i = 2; i <= n; ++i) Rank[SA[i]] = tp[SA[i]] == tp[SA[i - 1]] && tp[SA[i] + len] == tp[SA[i - 1] + len] ? p : ++p;
	}
}

此外，必须一提的是，后缀数组的构建方法并不止倍增法这一种，SA-IS和DC3两种算法都能在$\mathcal {O} (n)$的复杂度内构建出后缀数组，但由于本人太菜不会，这里就不做更多介绍了。

SA的性质

说完了后缀数组的构建方法，我们得了解它的一些有用的性质。可以说前面的所有都在为这一部分铺垫而已，以下后缀数组的真正精髓。

一些定义

$\text{lcp} (x, y)$：表示字符串$x$和字符串$y$的最长公共前缀

$height$数组：定义$height[i] = len(\text{lcp} (\text{Suffix} (SA[i - 1]), \text{Suffix} (SA[i])))$，即排名相邻的后缀的最长公共前缀长度。特别地，$height[1] = 0$

$H$数组：定义$H[i] = height[Rank[i]]$，即$i$号后缀与其前一名后缀的最长公共前缀长度

有一个比较显然的事实：对于满足$Rank[i] < Rank[j]$的$(i, j)$，有
$$
lcp(i, j) = \min ^j _ {k = i + 1} \left( height[Rank[k]] \right)
$$
感性理解一下就行了吧

height数组求法

首先给出一个定理
$$
H[i] \ge H[i - 1] - 1
$$
证明（部分引自论文）：

​ 首先$H[i - 1] \le 1$时显然成立

​ 否则，假设$\text{Suffix} (k)$是排在$\text{Suffix} (i - 1)$前一名的后缀，那么他们的$\text{lcp} $长度为$H[i - 1]$。因为$H[i - 1] > 1$（这很关键），所以$\text{Suffix} (k + 1)$一定会排在$\text{Suffix} (i)$之前（由$\text{Suffix} (k)$和$\text{Suffix} (i - 1)$各自去掉首位，这对排名的相对关系不会有影响），并且我们还能发现$\text{lcp} (\text{Suffix(k + 1)},\text{Suffix(i)})$为$H[i - 1] - 1$，同样从去掉首位得来。那么为什么$H[i]$一定不小于$H[i - 1] - 1$呢？可以肯定的一点是，排在$\text{Suffix} (i)$前一名的后缀一定会比$\text{Suffix(k + 1)}$更加靠近$i$（除非$k$就是$i$的前一名），并且排名离$\text{Suffix(i)}$更近的后缀与$i$的相似度一定会更高，因此$H[i - 1] - 1$为下界，原命题得证。

知道了这个定理后有什么用呢？

根据$H[i] \le H[i - 1] - 1$可以发现$H$数组是近乎单调的，我们因此便可$\mathcal{O}(n)$求出$H$数组，进而求出$height$数组。

height构建部分代码

1
2
3
4
5
6
7
8
9
void Build_Height() {
    int H = 0;
    for (int i = 1; i <= n; ++i) {
        if (Rank[i] == 1) continue;
        if (H > 0) --H;
        for (int j = SA[Rank[i] - 1]; str[i + H] == str[j + H]; ++H);
        height[Rank[i]] = H;
    }
}

SA的应用

当然，只有应用的多样性才能说明$SA$的强大

  1. 最长公共前缀

    给定一个字符串，询问某两个后缀的最长公共前缀

    上文已有提及，为$\displaystyle \min _{i = Rank[x] + 1} ^ {Rank[y]} height[i]$，转化为区间最值问题，用$\text{RMQ}$可做到$\mathcal {O} (1)$。

  1. 可重叠最长重复字串

    给定一个字符串，求出最长的重复出现的子串。可重叠

    因为可重叠，答案就是$height$数组中的最大值。

  1. 不可重叠最长重复字串

    给定一个字符串，求出最长的重复出现的子串。不可重叠

    比前一个稍微麻烦些。二分答案，判断有没有重复出现的长度为$k$的子串。首先将排序后的后缀进行分组（如下图），每一组之间$height$值不小于$k$，那么对于同一组的后缀，如果出现的$SA$的最大值与最小值之差同样不小于$k$，则存在（$SA$的差可视为后缀间的距离，注意只需一组满足即可）。

img

  1. 可重叠的$k$次最长重复字串

    给定一个字符串，求至少出现$k$次的最长重复子串。可重叠

    同样二分答案并进行分组。如果某一组中有至少$k$（题目中的$k$）个后缀，则存在。

  2. 不相同子串的个数

    给定一个字符串，求不相同的子串的个数

    每个子串唯一对应某个后缀的前缀。考虑一个后缀$i$对答案的贡献。它在不计重复的情况下会产生$n - i + 1$个前缀，即子串。而其中重复的个数为$H[i] = height[Rank[i]]$，即与排在它前面的后缀的$\text{lcp}$长度。从而答案为$\displaystyle \sum _ {i = 1} ^ n n - i + 1 - height[Rank[i]]$

  3. 第$k$大子串

    给定一个字符串，求出其字典序第$k$大子串

    从小到大枚举$SA_i$，这个后缀会产生$n - SA_i + 1 - height[i]$个不同子串，若大于$k$则输出，否则将$k$减去即可。

  4. 最长回文子串

    给定一个字符串，求其最长回文子串

    我们将字符串倒过来接在原串后面（中间隔上特殊字符），然后枚举每一位，对原串和反串的相应后缀求$\text{lcp}$，取最大值即可。具体可参考下图。

uR0HSJ.jpg

  1. 最长公共子串

    给定两个字符串$A$和$B$，求它们的最长公共子串

    做法同回文串有异曲同工之妙。将$B$串接在$A$串后面，以特殊字符相隔，枚举每一名后缀，如果它的前一名和它来自不同的字符串，那么就以$height$值更新答案。

常用的就这些了。。。吧？当然这只是后缀数组的应用中最基础的一部分，这里只做简短的介绍。总而言之，后缀数组是非常棒的字符串结构，在处理一类字符串问题时都有非常好的效果。值得掌握。

参考文献

IOI2009国家集训队论文：后缀数组-处理字符串的有力工具

另一篇帮助很大的文章：后缀数组详解-自为风月马前卒