后缀数组-模板详解

定义

给定字符串s，定义suffix(i)表示以s[i]开头的后缀，例如abcde的后缀suffix(2) = cde，如果s的长度为n，则s共有n个后缀，整数i表示后缀suffix(i)，将这n个后缀按照字典序从小到大排序，便形成了后缀数组sa，其中sa[i] = j 表示排序后s的后缀suffix(j)排在位置i。例如

s = abdcd

// s 的各个后缀
suffix(0) = abdcd
suffix(1) =  bdcd
suffix(2) =   dcd
suffix(3) =    cd
suffix(4) =     d

// 根据字典序从小到大排序
0: suffix(0) = abdcd
1: suffix(1) = bdcd
2: suffix(3) = cd
3: suffix(4) = d
4: suffix(2) = dcd

// sa 数组
sa[0] = 0
sa[1] = 1
sa[2] = 3
sa[3] = 4
sa[4] = 2
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22

那么，我们需要一个高效且编码难度适中的算法求解sa数组

模板

参考博客:破解外星代码：详解后缀数组模板

int wa[N], wb[N], wv[N], ws[N];

inline bool cmp(int *r, int a, int b, int len, int n) {
    if (r[a] != r[b]) return false;
    a = (a + len < n ? r[a + len] : -1); // 我们是从 0 开始排名的，越界的情况下值为 -1
    b = (b + len < n ? r[b + len] : -1);
    return a == b;
}

void SA(char *s, int *sa, int n, int m) {
    int i, j, p, *x = wa, *y = wb, *t;
    for (i = 0; i < m; i++) ws[i] = 0;
    for (i = 0; i < n; i++) ws[x[i] = s[i]]++;
    for (i = 1; i < m; i++) ws[i] += ws[i - 1];
    for (i = n - 1; i >= 0; i--) sa[--ws[x[i]]] = i;
    
    for (j = p = 1; p < n; j <<= 1, m = p) {
        for (p = 0, i = n - j; i < n; i++) y[p++] = i;
        for (i = 0; i < n; i++) if (sa[i] >= j) y[p++] = sa[i] - j;
        for (int i = 0; i < m; i++) ws[i] = 0;
        for (int i = 0; i < n; i++) ws[wv[i] = x[y[i]]]++;
        for (int i = 1; i < m; i++) ws[i] += ws[i - 1];
        for (int i = n - 1; i >= 0; i--) sa[--ws[wv[i]]] = y[i];

        for (t = x, x = y, y = t, x[sa[0]] = 0, p = i = 1; i < n; i++)
            x[sa[i]] = cmp(y, sa[i - 1], sa[i], j, n) ? p - 1: p++;
    }
}
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

0、说明

此模板利用倍增法求解sa数组。sa数组表示s各个后缀排序后的结果，为了方便描述，我们定义

• suffix(i, k) 为字符串 s 以 s[i] 开始的长度为 k 的后缀，长度不足则用字符0填充
• sa(k) 为 s 的所有 k 后缀的排序结果。

先求 sa(2 ^ 0) 再求 sa(2 ^ 1) …，如何在 sa(2 ^ i) 的基础上求出 sa(2 ^ (i + 1)) 是倍增算法的核心，这个地方使用了基数排序，我们会在接下来的分析中进行说明，现在就开始逐步分析这份代码吧。

1、求 sa(1)

sa(1)，求s的各个1后缀的排序结果，s的1后缀不就是s的每个字符吗？

    for (i = 0; i < m; i++) ws[i] = 0;
    for (i = 0; i < n; i++) ws[x[i] = s[i]]++;
    for (i = 1; i < m; i++) ws[i] += ws[i - 1];
    for (i = n - 1; i >= 0; i--) sa[--ws[x[i]]] = i;
1
2
3
4

上面这段代码就是求sa(1)的，我们先明确这几个变量的作用

• x[]: 记录 k 后缀的值，sa(k)数组不就是各个k后缀按照字典序从小到大排列形成的吗?那么值小的后缀在前，值大的在后。有了sa(k)为啥还需要x[]?sa(k)排在前面的后缀的值是小于等于排在后面的后缀，仅仅使用sa(k)我们无法判断到底是小于还是等于，因此需要增加一个x[]，针对两个 k 后缀 i、j，根据 x[i] 和 x[j] 的大小关系，便可知道后缀 i 与后缀 j 的大小关系。此处 k = 1，即 x[i] 表示字符 s[i] 的值，在 C/C++ 中字符的值就是其对应的 ASCII 码，其值的大小关系符合字典序，因此在遍历字符的过程中，我们将1后缀的值直接设置为字符的值，即x[i] = s[i]
• m: 我们利用计数排序将1后缀排好序，m 就是我们有多少个不同的值，将各个字符排序我们一般用128
• ws[]: 计数排序用的统计数组，记录各个值出现的次数
• sa[]: 记录 k 后缀从小到大排序的结果，此时k = 1

介绍完各个变量，现在就梳理这段代码了

• 1、将计数排序用的数组 ws[] 全置为 0
• 2、遍历字符串 s的每个字符，对应字符值出现次数加一，此处我们用 x[i] = s[i] 将1后缀的值设置为对应的字符值
• 3、计数数组求前缀，用于后续求排名
• 4、从后往前遍历s的每个字符，suffix(i, 1) 的值为x[i]，对应的排名为--ws[x[i]]，从后往前遍历是为了对于后缀值相同的后缀，排在后面的后缀对应的排名更大，--ws[x[i]] 先减是因为我们排名是从0开始计的。

2、求 sa(2)

如何在 sa(1) 的基础上求解 sa(2)? 我们注意到 suffix(i, 2) 是由两部分组成：suffix(i, 1)、suffix(i + 1, 1), 这两个后缀的值分别为 x[i]、x[i + 1]，设这两部分的值分别为第一关键字和第二关键字，此处我们利用基数排序，先根据第二关键字从小到大排序，再根据第一关键字从小到大排序，最后便可得到所有的 2后缀的排序结果。

        for (p = 0, i = n - j; i < n; i++) y[p++] = i;
        for (i = 0; i < n; i++) if (sa[i] >= j) y[p++] = sa[i] - j;
        for (int i = 0; i < m; i++) ws[i] = 0;
        for (int i = 0; i < n; i++) ws[wv[i] = x[y[i]]]++;
        for (int i = 1; i < m; i++) ws[i] += ws[i - 1];
        for (int i = n - 1; i >= 0; i--) sa[--ws[wv[i]]] = y[i];
1
2
3
4
5
6

这段代码用于求解 sa(2)。同样的步骤，我们先分析各个变量的作用。

• j：表示 sa(j) ,即 j 后缀的排序结果已经计算出来了，正在求解 sa(2 * j)，此时 j = 1，sa(1) 已经计算出来，正在计算 sa(2) 。
• ws[]: 同上，用于计数排序的统计数组。
• y[]: 所有的 2后缀仅根据第二关键字从小到大排序的结果。
• p: 生成y数组的下标计数。
• wv[]: 按照第二关键字从小到大排序的后缀的第一关键字的值。
• x[]: 记录所有的 suffix(i, 1), 即所有的 1 后缀的值，这里仅使用，后续才更新。

分析完变量后，我们开始分析这段代码。

生成 y[]，一开始不太明白第一条代码，看了几篇博客后才明白它的含义，y[] 的定义是所有的 2 后缀仅根据第二关键字从小到大排序的结果，那么如果第二关键字不存在，则将第二关键字视为最小，因此这些后缀排在 y[] 的前面，i >= n - j 的后缀的第二关键字均不存在，因此排在前面。

然后遍历整个 sa(1)，相当于从小到大遍历第二关键字，其对应的 2 后缀起始位置则为 sa[i] - j

        for (p = 0, i = n - j; i < n; i++) y[p++] = i;
        for (i = 0; i < n; i++) if (sa[i] >= j) y[p++] = sa[i] - j;
1
2

求出 y[] 后，我们已经按照第二关键字将 2 后缀排序好了，接下来再根据第一关键字将后缀从小到大排序，则能得到 sa(2) 的结果。

        for (int i = 0; i < m; i++) ws[i] = 0;
        for (int i = 0; i < n; i++) ws[wv[i] = x[y[i]]]++;
        for (int i = 1; i < m; i++) ws[i] += ws[i - 1];
        for (int i = n - 1; i >= 0; i--) sa[--ws[wv[i]]] = y[i];
1
2
3
4

• 1、先将计数排序用的统计数组置 0
• 2、按第二关键字排序的顺序(y[] 的顺序)遍历每个 2 后缀，将后缀对应的第一关键字对应的值（x[y[i]]）出现次数加一，并在遍历的过程中，将后缀对应的值用 wv[] 保存，即 wv[i] = x[y[i]]
• 3、求统计数组的前缀和，便于后续求排名
• 4、同求 sa(1)一样，为保证稳定排序，我们按第二关键字排序的逆序(y[] 的逆序)遍历每个 2 后缀，后缀对应的第一关键字的值为 x[y[i]] 即第2步保存的 wv[i]，遍历后变得出了 sa(2)

sa(2) 已经求出来了，下一步就是求解 sa(4) 了，但是在求 sa(4) 之前我们需要做准备工作，4 后缀 suffix(i, 4) 也是由两部分构成suffix(i, 2) 和 suffix(i + 2, 2)，两个关键字分别为 2 后缀的值，但是目前 x[] 是各个1 后缀的值，我们需要将 x[] 更新为所有 2 后缀的值。更新代码如下

        for (t = x, x = y, y = t, x[sa[0]] = 0, p = i = 1; i < n; i++)
            x[sa[i]] = cmp(y, sa[i - 1], sa[i], j, n) ? p - 1: p++;
1
2

2 后缀的值是根据 1 后缀的值以及sa(2) 求出来的，sa(2)中排在前面的2后缀的值小于等于排在后面的2后缀，那么我们从前往后遍历sa(2)数组，然后再根据1后缀的值判断前后两个2后缀的值是否相等，这样就可以求出所有 2 后缀的值了。这里需要注意一点，后缀的值其实就是指符合字典序的大小关系，我们可以从 0 开始赋值，从前往后遍历 sa(2) 数组时，如果当前后缀和前一个后缀相同，则赋同样的值，否则赋更大的值。判断两个后缀是否相同其实很简单，只要比较两个后缀对应的第一、第二关键字是否相同即可。代码如下

inline bool cmp(int *r, int a, int b, int len, int n) {
    if (r[a] != r[b]) return false;
    a = (a + len < n ? r[a + len] : -1); // 我们是从 0 开始排名的，越界的情况下值为 -1
    b = (b + len < n ? r[b + len] : -1);
    return a == b;
}
1
2
3
4
5
6

由于 x[] 是需要更新的值，同时在更新的过程中又需要旧x[] 中的值，因此我们交换x[]，y[]，那么在更新的过程中使用y[]的数据即可。更新完毕后，p 的值就是所有2后缀中不同的值的数量，继续进行下一轮循环。

for (j = p = 1; p < n; j <<= 1, m = p)
1

j 从1 变成 2，m 更新为 p（即不同的后缀值的个数），注意循环结束的条件是 p == n，即不同的后缀值的个数有 n 个，当出现n个不同后缀值时，说明各个后缀已经排好序了，因此便可退出循环。

至此，分析完毕，求出 sa 数组后，我们便可利用 sa 做一些有趣的事了。