后缀数组(SA)学习笔记

Posted on | In |
Words count in article: 1.6k | Reading time ≈ 6

后缀数组（SA）学习笔记

什么是后缀数组

后缀数组，顾名思义就是与一个字符串的后缀串有关的神奇玩意

那么什么又是字符串的后缀串呢？

我们假设有一个长为 $len$ 的字符串 $s$ ，我们把从第 $i$ 个位置到第 $len$ 个位置的这一段子串称为第 $i$ 个位置的后缀 ( $Suffix_i$ ) 。

然后我们需要知道一点：后缀数组严格说来并不能算是某种特定的算法，算是一种思想(?) 。

后缀数组能干些什么

如果你会后缀自动机（ $\text{SAM}$ ）的话，后缀数组的用处自然并不是太大，不过也有一些后缀自动机不能做而后缀数组能做的事情，比如说下面这个题：

有一个01串 $s$ ，定义一个前缀最右边的位置为这个前缀的结束位置，有 $q$ 个询问，每次询问结束位置在区间 $[l, r]$ 中不同前缀的最长公共后缀是多长。（ $|s|, q \leq 10^5$ ）

现在你可能不会这道题，但是相信你看完这篇文章后一定会有一些思路。

构造后缀数组（SA）

一些将会用到的变量

为了避免在下文中讲到一半突然开始解释变量含义这种毒瘤事情的发生，所以我决定把东西在这里讲清楚。

  • $a$ ：表示被处理的字符串
  • $Suffix_i$ ：如上文所述
  • $rk_i$ ：表示 $Suffix_i$ 在所有后缀中的排名。
  • $SA_i$ ：表示排名为 $i$ 的后缀的起点在原串中的位置

好了，基本的东西列完了，来感性理解一下。

后缀数组实质上指的就是这个 $SA$ 。由定义可知 $SA$ 与 $rk$ 有以下关系：

总之两数组就是互逆的。然后有了这个东西我们就能开始搞一些神仙玩意了（反正我不会.jpg

然后我们来讲如何求 $SA$ 。

倍增算法

目前两种主流算法之一，主要思想：对于一个 $Suffix_i$ ，想直接知道它的 $rk$ 比较困难，但是我们可以对每个字符开始的长度为 $2^k$ 的字符串求出排名， $k$ 从0开始每次递增1，直到求出所有数的排序为止。

具体的做法如下图所示：

实际上只要理解了字符串的比较法则，就并不难理解上面的那张图。所以问题就只剩下了一个：如何进行排序。快排吗？复杂度是 $O(logn)$ 的快排会使最后的复杂度变为 $O(log^2n)$ ，就并没有什么优越性了。所以我们引入一种新的排序方法：基数排序（Radix Sort）。

基数排序

什么是基数排序

基数排序是一种能够在 $O(n)$ 复杂度内对 $n$ 个元素进行排序的算法（虽然常数很大），如果压位的话可以跑得非常快，再加上一些奇技淫巧就更加香港记者了。wys在挑战一题中的 $subtask1$ 即可使用毒瘤卡常基排通过（

基数排序的原理

基数排序的原理大概就是对每一位进行一次桶排，以当前位为第一关键字，上一位为第二关键字进行双关键字排序。

大概过程就在VisuAlgo上看一下动画就懂了吧（懒得讲.jpg

模板代码

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
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
#include <bits/stdc++.h>
#define ri register int
#define il inline
using namespace std;

typedef long long ll;
typedef unsigned long long ull;

const int N = 1e6 + 110;
const int MAXN = 110;
const int inf = 0x7fffffff;
const double eps = 1e-8;

il int read()
{
    int x = 0, f = 1;
    char ch = getchar();
    while (!isdigit(ch))
    {
        if (ch == '-')
            f = -1;
        ch = getchar();
    }
    while (isdigit(ch))
    {
        x = (x << 3) + (x << 1) + ch - '0';
        ch = getchar();
    }
    return x * f;
}

char s[N];

namespace Suffix_Array
{
    int n, m;
    int rk[N], SA[N], tmp[N], tax[N], a[N];
    char s[N];

    const int maxm = 1005;

    il void Init()
    {
        scanf("%s", s + 1);
        n = strlen(s + 1);
        for (ri i = 1; i <= n; i++)
            a[i] = (int)s[i];
    }

    il void Radix_Sort(int m)
    {
        memset(tax, 0, sizeof(int) * (m + 1));
        for (ri i = 1; i <= n; i++)
            tax[rk[i]]++;
        for (ri i = 2; i <= m; i++)
            tax[i] += tax[i - 1];
        for (ri i = n; i; i--)
            SA[tax[rk[tmp[i]]]--] = tmp[i];
    }

    il bool cmp(int *a, int x, int y, int w)
    {
        return a[x] == a[y] && (x + w > n ? -1 : a[x + w]) == (y + w > n ? -1 : a[y + w]);
    }

    il void Build()
    {
        for (ri i = 1; i <= n; i++)
            rk[i] = a[i], tmp[i] = i;
        m = maxm;
        Radix_Sort(m);
        for (ri p = 1, w = 1; p < n; m = p, w <<= 1)
        {
            p = 0;
            for (ri i = n - w + 1; i <= n; i++)
                tmp[++p] = i;
            for (ri i = 1; i <= n; i++)
                SA[i] > w ? tmp[++p] = SA[i] - w : 0;
            Radix_Sort(m);
            for (ri i = 1; i <= n; i++)
                tmp[i] = rk[i];
            rk[SA[1]] = p = 1;
            for (ri i = 2; i <= n; i++)
                rk[SA[i]] = cmp(tmp, SA[i], SA[i - 1], w) ? p : ++p;
        }
    }
    il void print()
    {
        for (ri i = 1; i <= n; i++)
            printf("%d ", SA[i]);
    }
}

int main()
{
    Suffix_Array :: Init();
    Suffix_Array :: Build();
    Suffix_Array :: print();
    return 0;
}

DC3算法

由于我不会，所以不讲（咕咕咕

求Height数组

当然，如果只有上面这些东西的话你除了能过洛谷上的板子题外什么也干不了，所以接下来我们来讲一下真正能让后缀数组发挥用处的东西。

一些将会用到的变量

  • $Height_i$ ：表示 $Suffix[SA[i]]$ 与 $Suffix[SA[i - 1]]$ 的最长公共前缀，也就是排名相邻的两个后缀的最长公共前缀。
  • $H_i$ ：等价于 $Height[rk[i]]$ ，也就是后缀 $Suffix_i$ 和它前一名后缀的最长公共前缀。

两个排名不相邻的后缀的最长公共前缀定义为排名在它们之间的 $Height$ 的最小值。

先形象的理解一下：

高效求得Height数组

首先如果在 $SA$ 中顺序比较的话复杂度是 $O(n^2)$ 的，还是什么都干不了，所以我们利用 $H$ 数组的一个性质来快速求得 $Height$ 。

证明如下：

假设 $Suffix[k]$ 是排在 $Suffix[i-1]$ 前一名的后缀，则它们最长的公共前缀是 $H[i-1]$ 。都去掉第一个字符，就变成了 $Suffix[k+1]$ 与 $Suffix[i]$ 。如果 $H[i-1]$ 为0或1，那么 $H[i]\geq0$ 显然成立；否则 $H[i]\geq H[i-1]-1​$ 。（都去掉了第一个字符，其他前缀都相等）至此得证。

那么我们就可以按照 $H_1,H_2,H_3,…,H_n$ 进行计算，复杂度 $O(n)$ 。

模板代码

咕咕咕（

总结

咕咕咕

0%