「知识总结」后缀数组【后缀数组】

简介

后缀数组是一种处理字符串的有力工具。它通过对字符串的后缀进行处理,能够方便地得到子串的信息。

定义

nn 为字符串 ss 的长度。

后缀:suffix[i]\text {suffix}[i] 表示字符串 ss 从第 ii 个位置开始的后缀,即由 s[i]s[i] ~ s[n1]s[n-1] 组成的子串。

后缀数组:SA\text {SA} 是一个一维数组,保存了对 ss 的所有后缀排序后的结果。SA[i]\text {SA}[i] 表示第 ii 小的后缀在原串中的起始位置。

名次数组:rank\text {rank} 是一个一维数组,按起始位置保存了每个后缀在 SA\text {SA} 中的排名。rank[i]\text {rank}[i] 表示 suffix[i]\text {suffix}[i] 的排名,即 rank[SA[i]]=i\text {rank}[\text {SA}[i]] = i

高度数组:height\text {height} 是一个一维数组,保存了排名相邻的两个后缀的最长公共前缀的长度。即 height[i]\text {height}[i] 表示存在最大的 xx,满足对于任何 k[0,x)k\in [0, x)s[SA[i]+k]=s[SA[i1]+k]s[\text {SA}[i] + k]=s[\text {SA}[i-1] + k]

后缀数组

一般使用倍增算法来求出后缀数组。它的主要思路是:每次利用上一次的结果,倍增计算出从每个位置 ii 开始长度为 2k2^k 的子串的排名。

首先求出从每个位置开始,长度为 20=12^0 = 1 的子串的排名。

为了求出长度为 2k2^k 的子串的排名,可以用从位置 ii 开始且长度为 2k12^{k-1} 的子串为第一关键字,从位置 i+2k1i+2^{k-1} 开始且长度为 2k12^{k-1} 的子串为第二关键字,进行双关键字排序。对于 i+2k1ni+2^{k-1} \geqslant n 的位置,用一个比其他所有值都小的数作为它的第二关键字,例如 1-1

如果用快速排序来实现双关键字排序,那么总时间复杂度为 O(nlog2n)O(n\cdot \log ^2n)。考虑到每个关键字均为 [1,n)[-1, n) 的整数,所以可以使用 O(n)O(n) 的基数排序,这样就将总时间复杂度降为 O(nlogn)O(n\cdot \log n)

高度数组

后缀数组的大部分应用,都需要高度数组 height\text {height} 的辅助。如果按照定义去计算 height\text {height} 数组,最坏的时间复杂度为 O(n2)O(n^2),无法承受。

h[i]=height[rank[i]]h[i] = \text {height}[\text {rank}[i]],也就是 suffix[i]\text {suffix}[i] 和在它前一名的后缀的最长公共前缀。则 h[i]h[i] 有如下性质:h[i]h[i1]1h[i] \geqslant h[i-1]-1,证明略。

按照 h[1],h[2],h[n]h[1], h[2], \cdots h[n] 的顺序计算,并利用 hh 数组的性质, 时间复杂度可以降为 O(n)O(n)。其实在实现时没有必要保存 hh 数组,只需按照顺序计算即可。注意 height[0]\text {height}[0] 的值是无效的。

最长公共前缀

题目描述:给定一个字符串,询问某两个后缀的最长公共前缀。

思路分析:求两个后缀的最长公共前缀可以转化为求某个区间上的最小的 height\text {height} 值。对于这个区间最值查询问题,可以使用稀疏表 (Sparse Table\text {Sparse Table}) 解决。该算法的预处理时间为 O(nlogn)O(n \cdot \log n),单次查询为 O(1)O(1)

后缀数组的实现样例

Description

读入一个长度为 nn 的由小写英文字母组成的字符串,请把这个字符串的所有非空后缀按字典序从小到大排序,然后按顺序输出后缀的第一个字符在原串中的位置。位置编号为 11nn。除此之外为了进一步证明你确实有给后缀排序的超能力,请另外输出 n1n-1 个整数分别表示排序后相邻后缀的最长公共前缀的长度。

Solution

注意在倍增算法中基数排序的写法。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
#include <bits/stdc++.h>
using namespace std;

const int maxn = 1e5 + 10;
char s[maxn];
int n, sa[maxn], rk[maxn], ht[maxn];
int num[maxn], a[maxn];
int fir[maxn], sec[maxn], buc[maxn], tmp[maxn];

void build_sa() {
copy(s + 1, s + n + 1, num + 1);
sort(num + 1, num + n + 1);
int *end = unique(num + 1, num + n + 1);
for (int i = 1; i <= n; i++) a[i] = lower_bound(num + 1, end, s[i]) - num;
memset(buc, 0, sizeof(buc));
for (int i = 1; i <= n; i++) buc[a[i]]++;
for (int i = 1; i <= n; i++) buc[i] += buc[i - 1];
for (int i = 1; i <= n; i++) rk[i] = buc[a[i] - 1] + 1;
for (int k = 1; k <= n; k <<= 1) {
for (int i = 1; i <= n; i++) fir[i] = rk[i];
for (int i = 1; i <= n; i++) sec[i] = i + k > n ? 0 : rk[i + k];
memset(buc, 0, sizeof(buc));
for (int i = 1; i <= n; i++) buc[sec[i]]++;
for (int i = 1; i <= n; i++) buc[i] += buc[i - 1];
for (int i = 1; i <= n; i++) tmp[n - --buc[sec[i]]] = i;
memset(buc, 0, sizeof(buc));
for (int i = 1; i <= n; i++) buc[fir[i]]++;
for (int i = 1; i <= n; i++) buc[i] += buc[i - 1];
for (int i = 1; i <= n; i++) sa[buc[fir[tmp[i]]]--] = tmp[i];
bool unique = true;
rk[sa[1]] = 1;
for (int i = 1; i <= n; i++) {
rk[sa[i]] = rk[sa[i - 1]];
if (fir[sa[i]] == fir[sa[i - 1]] && sec[sa[i]] == sec[sa[i - 1]]) unique = false;
else rk[sa[i]]++;
}
if (unique) break;
}
for (int i = 1, k = 0; i <= n; i++) {
if (k) k--;
int j = sa[rk[i] - 1];
while (i + k <= n && j + k <= n && a[i + k] == a[j + k]) k++;
ht[rk[i]] = k;
}
}

int main() {
scanf("%s", s + 1);
n = strlen(s + 1);
build_sa();
for (int i = 1; i <= n; i++) printf("%d%c", sa[i], " \n"[i == n]);
for (int i = 2; i <= n; i++) printf("%d%c", ht[i], " \n"[i == n]);
return 0;
}

总结

后缀数组的时间复杂度为 O(nlogn)O(n \cdot \log n),使用倍增算法求出。由于倍增算法时间复杂度较为优秀,并且实现难度不高,所以在实践中较为常用。应掌握后缀数组这种数据结构,并且能在不同类型的题目中灵活、高效的运用。