后缀数组 学习笔记

1. 在字符串\(S\)中，第\(i\)个字符到第\(j\)个字符（包括\(i,j\)）组成的子串记作\(S[i,j]\)。
2. 在字符串\(S\)中，第\(i\)个字符开始的后缀记作\(\text{Suffix}(i)\)。
3. 记\(SA[i]\)表示字符串\(S\)的所有后缀从小到大排序后，第\(i\)个后缀的开始位置。\(SA\)即后缀数组。
4. 记\(rank[i]\)表示字符串\(S\)的第\(i\)个后缀从小到大的排名，即\(SA\)的逆数组。

下面给出一个例子（字符串下标从\(1\)开始）：

1
2
3
4
5
6
7
8
9
10
11

String S:  a a b a a a a b
    Rank:  4 6 8 1 2 3 5 7
--------------------------
SA[1]=4 -> a a a a b
SA[2]=5 -> a a a b
SA[3]=6 -> a a b
SA[4]=1 -> a a b a a a a b
SA[5]=7 -> a b
SA[6]=2 -> a b a a a a b
SA[7]=8 -> b
SA[8]=3 -> b a a a a b

由于\(rank\)是\(SA\)的逆数组，在求出\(SA\)数组后，我们可以\(\mathcal O(|S|)\)求出\(rank\)数组，即rank[sa[i]]=i。

设字符串长度为\(n\)且下标从\(1\)开始。

我们直接把\(S\)的每个后缀求出，然后用任意一种排序方法，在比较时暴力\(\mathcal O(n)\)比较两个后缀的大小即可。

这种方法的复杂度太劣，我们尝试优化。

前置知识

倍增，基数排序。

由于基数排序较为简单，这里不详细讲。

算法思想

倍增算法的主要思想是：用倍增的方法对每个字符开始长度为\(2^k\)的子串进行排序，求出排名。\(k\)从\(0\)开始，直到\(2^k>n\)时，这些子串就是\(S\)的所有后缀。

可以发现，如果我们能\(\mathcal O(n)\)求出每个字符开始长度为\(2^k\)的子串排序后的结果，那么此算法的复杂度就是\(\mathcal O(n\log n)\)的。

考虑利用\(k-1\)时的排序结果快速求出当前结果。

由于我们已经求出每个字符开始长度为\(2^{k-1}\)的子串的排名，那么字符串的比较变成了排名的比较。

这是一个双关键字排序，设当前字符为\(i\)，则第一关键字为\(i\)开始长度为\(2^{k-1}\)的子串的排名，第二关键字为\(i+2^k\)开始长度为\(2^{k-1}\)的子串的排名。

如果用快速排序，则总复杂度为\(\mathcal O(n\log^2 n)\)。

由于排名的值不会超过\(n\)，我们考虑用基数排序做到总复杂度为\(\mathcal O(n\log n)\)。

双关键字的基数排序只要先按照第二关键字从小到大排序，再按照第一关键字从小到大排序即可，都可以做到\(\mathcal O(n)\)的复杂度。

算法实现

技巧

直接基数排序的常数较大，我们考虑每次把排序后的结果暂存在\(SA\)数组中，即当前的\(SA[i]\)表示每个字符开始长度为\(2^k\)的子串进行排序后，排名为\(i\)的子串的起始位置。

这样一来，我们可以利用\(k-1\)时求出来的\(SA\)数组，直接按第二关键字排好序，再按第一关键字排序。

代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24

int sa[N], tx[N], ty[N], cnt[N];
void Radix_Sort(int n, int m, int *x, int *y, int *sa){
    for (register int i = 0; i <= m; ++i) cnt[i] = 0;
    for (register int i = 1; i <= n; ++i) ++cnt[x[i]];
    for (register int i = 1; i <= m; ++i) cnt[i] += cnt[i - 1];
    for (register int i = n; i; --i) sa[cnt[x[y[i]]]--] = y[i];
}
bool cmp(int *a, int x, int y, int l){
    return a[x] == a[y] && a[x + l] == a[y + l];
}
void Get_SA(int n, int m, int *a, int *sa){
    int *x = tx, *y = ty;
    for (register int i = 1; i <= n; ++i) x[i] = a[i], y[i] = i;
    Radix_Sort(n, m, x, y, sa);
    for (register int j = 1, p = 0; p < n; j <<= 1, m = p){
        p = 0;
        for (register int i = n - j + 1; i <= n; ++i) y[++p] = i;
        for (register int i = 1; i <= n; ++i) if (sa[i] > j) y[++p] = sa[i] - j;
        Radix_Sort(n, m, x, y, sa);
        std :: swap(x, y), p = 1, x[sa[1]] = 1;
        for (register int i = 2; i <= n; ++i)
            x[sa[i]] = cmp(y, sa[i - 1], sa[i], j) ? p : ++p;
    }
}

代码解释

代码中的\(x[i]\)表示\(i\)开始长度为\(j=2^k\)的子串排序后的排名，\(y[i]\)在前半部分表示按第二关键字排序后，排名为\(i\)的子串的起始位置。

Radix_Sort函数即基数排序，不详细阐述。

1
2
3

int *x = tx, *y = ty;
for (register int i = 1; i <= n; ++i) x[i] = a[i], y[i] = i;
Radix_Sort(n, m, x, y, sa);

这三行是初始化，由于长度为\(1\)，直接按照字符本身为第一关键字进行排序，\(y[i]=i\)时表示没有第二关键字。

1
2
3
4
5

for (register int j = 1, p = 0; p < n; j <<= 1, m = p){
    p = 0;
    for (register int i = n - j + 1; i <= n; ++i) y[++p] = i;
    for (register int i = 1; i <= n; ++i) if (sa[i] > j) y[++p] = sa[i] - j;
    Radix_Sort(n, m, x, y, sa);

\(j\)枚举的是\(\frac{2^k}{2}\)的值，即当前需要排序的子串长度的一半。首先把第二关键字为\(0\)的位置加入\(y\)。然后按第二关键字从小到大的加入\(y\)。为什么可以这样写？因为\(sa[i]\)表示排名为\(i\)的子串的初始位置，即\(sa[i]\)的排名一定是除\(0\)外第\(i\)小的，而以\(sa[i]\)的排名作为第二关键字的位置就是\(sa[i]-j\)，所以这样做就是把位置按第二关键字从小到大的加入\(y\)。

1
2
3
4

    std :: swap(x, y), p = 1, x[sa[1]] = 1;
    for (register int i = 2; i <= n; ++i)
        x[sa[i]] = cmp(y, sa[i - 1], sa[i], j) ? p : ++p;
}

这一段代码中，由于前面的\(y\)数组毫无用处了，就交换\(x,y\)，使得\(y\)表示上一个\(j\)时的排名，把\(x\)更新为当前\(j\)时的排名。这里不能直接写x[sa[i]]=i的原因是有些子串可能会相等，那么它们的排名也应该相等。\(p\)记录的是排名不同的子串数量，如果\(p=n\)则直接退出循环。

还有一种求后缀数组的算法，叫做\(\text{DC3}\)。该算法可以做到复杂度\(\mathcal O(n)\)建立后缀数组，但由于常数较大且代码复杂度较高，不推荐使用。

有兴趣的同学可以查阅参考资料\([1]\)。

在具体应用中，\(SA\)数组的应用并不多，更多的是另一个可以利用\(SA,rank\)数组求出的数组——\(height\)数组。

定义

\(height[i]\)表示\(\text{Suffix}(SA[i])\)和\(\text{Suffix}(SA[i-1])\)的最长公共前缀（Longest Common Prefix, LCP）。即排名相邻的两个后缀的\(\text{LCP}\)。

性质

性质一

对于任意\(i,j(rank[i]<rank[j])\)，\(\text{Suffix}(i)\)与\(\text{Suffix}(j)\)的\(\text{LCP}\)为\(\min\limits_{rank[i]<k\le rank[j]} height[k]\)。

这个性质比较显然，证明略。

性质二

记\(H[i]=height[rank[i]]\)。对于任意\(i>1\)，有\(H[i]\ge H[i-1]-1\)。

证明：当\(H[i-1]\le 1\)时显然。当\(H[i]>1\)时，假设排\(\text{Suffix}(i-1)\)前一名的后缀是\(\text{Suffix}(k)\)，则\(\text{Suffix}(i)\)与\(\text{Suffix}(k+1)\)的\(\text{LCP}\)为\(H[i-1]-1\)（相当于都去掉了第一位），且\(\text{Suffix}(k+1)\)也排\(\text{Suffix}(i)\)前面，则根据性质一，\(H[i]\)不会小于这个值，得证。

求法及代码实现

根据性质二，直接按照\(height[rank[1]],height[rank[2]],\cdots,height[rank[n]]\)的顺序求即可。

1
2
3
4
5
6

void Get_Height(int n, int *a, int *sa, int *rank, int *height){
    for (register int i = 1; i <= n; ++i) rank[sa[i]] = i;
    for (register int i = 1, k = 0, j; i <= n; height[rank[i]] = k, ++i)
        if (rank[i] > 1) for (k ? --k : 0, j = sa[rank[i] - 1]; a[i + k] == a[j + k]; ++k)
    height[1] = 0;
}

由于\(k\)最多减少\(n\)次，且不会超过\(n\)，所以时间复杂度为\(\mathcal O(n)\)。

给定一个字符串，\(q\)次询问某两后缀的最长公共前缀的长度。

解法

建出\(height\)数组后，根据\(height\)数组的性质一，原问题可以转化为区间最小值问题，直接用\(\text{ST}\)表维护即可。

时间复杂度\(\mathcal O(n\log n+q)\)。

若使用\(\text{DC3}\)算法求\(\text{SA}\)，\(\text{RMQ}\)问题\(\mathcal O(n)\)预处理，则时间复杂度为\(\mathcal O(n+q)\)。

更多的例题可以查阅参考资料\([1]\)。

1. IOI2009国家集训队论文《后缀数组——处理字符串的有力工具》，罗穗骞