后缀数组笔记

Posted on 2019-02-04 Views:

简介

后缀数组是字符串当中常见的一种数据结构，它将一个字符串的所有后缀进行排序，得到以下三个数组：

$\operatorname{sa}[i]$ ：排序后排名为的后缀的起始位置
$\operatorname{rank}[i]$ ：起始位置为的后缀的排名
$\operatorname{height}[i]$ ：起始位置 $\operatorname{sa}[i]$ 的后缀和起始位置 $\operatorname{sa}[i - 1]$ 的后缀的最长公共前缀长度

利用这三个数组我们可以有力地解决字符串当中的大部分问题。

构造

显然如果我们朴素地去构造长度为的字符串的后缀树组的话，时间复杂度为 $O(n^2\log n)$ 。这对于长字符串来说是完全无法接受的。然而利用倍增的思想我们可以在 $O(n\log n)$ 之内快速构造后缀树组，虽然像DC3，SAIS之类的 O(n) 算法也存在，但是倍增的编码难度更低，也足以通过大部分的题目（毕竟可能很多时候瓶颈不在于构造）。

$O(n\log n)$ 的构造代码如下：

void build_sa() {
    static int a[N], b[N], d[N], tmp[N], buc[N];
    copy(s + 1, s + 1 + n, d + 1);
    sort(d + 1, d + 1 + n);
    int *end = unique(d + 1, d + 1 + n);
    for (int i = 1; i <= n; i++) a[i] = lower_bound(d + 1, end, s[i]) - d;
    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 t = 1; t <= n; t *= 2) {
        copy(rk + 1, rk + 1 + n, a + 1);
        for (int i = 1; i <= n; i++) b[i] = i + t > n ? 0 : rk[i + t];
        
        fill(buc, buc + n + 1, 0);
        for (int i = 1; i <= n; i++) buc[b[i]]++;
        for (int i = 1; i <= n; i++) buc[i] += buc[i - 1];
        for (int i = n; i; i--) tmp[buc[b[i]]--] = i;

        fill(buc, buc + n + 1, 0);
        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 = n; i; i--) sa[buc[a[tmp[i]]]--] = tmp[i];

        bool flag = true;
        for (int i = 1, last = 0; i <= n; i++) {
            int p = sa[i];
            if (!last) rk[p] = 1;
            else if (a[p] == a[last] && b[p] == b[last])
                flag = false, rk[p] = rk[last];
            else rk[p] = rk[last] + 1;
            last = p;
        }
        if (flag) break;
    } 
}

其思想如下：如果我们先把所有后缀按照它们前 $2^{i - 1}$ 个字符进行排序，那基于排完序的结果我们就可以使用双关键字排序对所有后缀按照前 $2^{i}$ 个字符进行排序（原因是后缀的后缀还是后缀）,当然在实践过程中我们常使用桶排来加速这一个过程。

代码的最后一段是在 $\operatorname{rank}$ 互异的时候直接跳出，这是一个小优化。

计算 $\operatorname{height}[]$

除了朴素比较之外， $\operatorname{height}$ 数组的计算可以在 O(n) 时间内完成。

观察：设 $h[i] = \operatorname{height}[\operatorname{rank}[i]]$ ，则我们有：

$h[i] \ge h[i - 1] - 1$

证明：

：Trivial
：设 $k = \operatorname{sa}[\operatorname{rank}[i - 1]-1]$ 表示 $\operatorname{sa}$ 数组当中排在以为起始的后缀前的后缀的起始位置，以开始的后缀与以开始的后缀的LCP为。考虑统一截掉开头的一个字符，得到起始位置为与的两个后缀，其LCP为，在 $\operatorname{sa}[]$ 里面肯定排在前面，又因为后缀数组的性质，与 $\operatorname{sa}[\operatorname{rank}[i] - 1]$ 的LCP一定不会小于和的LCP，因此不等式成立。

基于以上的观察，计算 $\operatorname{height}[]$ 的代码如下：

for (int i = 1, k = 0; i <= n; i++) {
    if (rk[i] == 1) k = 0;
    else {
        if (k > 0) k--;
        int j = sa[rk[i] - 1];
        while (i + k <= n && j + k <= n && s[i + k] == s[j + k]) k++;
    }
    ht[rk[i]] = k;
}