后缀数组 & 后缀平衡树

PPT:【腾讯文档】后缀数组——钱贵宁

后缀数组

是什么

本质上是对一个字符串的所有后缀进行排序

例如字符串 abbcaba，我们按长度顺序列出它的所有后缀

1: a
2: ba
3: aba
4: caba
5: bcaba
6: bbcaba
7: abbcaba

然后我们按照字典序将它们排好序，用 sa[i] 表示第 i 小的后缀编号，rk[i] 表示第 i 个后缀的排名。显然 sa 数组和 rk 数组存在“互逆”的关系，即 sa[rk[i]] = i

sa[1] = 1: a       -> rk[1] = 1
sa[2] = 3: aba     -> rk[3] = 2
sa[3] = 7: abbcaba -> rk[7] = 3
sa[4] = 2: ba      -> rk[2] = 4
sa[5] = 6: bbcaba  -> rk[6] = 5
sa[6] = 5: bcaba   -> rk[5] = 6
sa[7] = 4: caba    -> rk[4] = 7

sa 数组和 rk 数组就是后缀数组中最常用的两个数组

例题：JSOI2007 字符加密

给一个字符串，将其首尾相连之后显然可以得到 n 个长度为 n 的新字符串，将这些新字符串依次排序，依次输出他们的末尾字符。

在输入的字符串后接上它本身，对新字符串利用后缀数组排序，只保留长度大于原字符串的后缀，就是所有待求字符串。

实现

P.S. 你可能听说过在大多数情况下后缀数组可以当作黑箱使用，不必完全理解实现方法。但是如果你打算尽量理解其含义，请不要尝试直接去看最优解法的代码，其代码的实现方法大概率会让你一头雾水。

这一部分主要是讨论如何求得 sa 和 rk 数组。

显然根据定义，我们可以直接去尝试排序。

char s[MAXN];//字符串
int len;//字符串长度
int sa[MAXN];
bool cmp(const int& a, const int& b)
{
    int ta = a, tb = b;
    while(ta <= len && tb <= len)
    {
        if(s[ta] != s[tb]) return s[ta] < s[tb];
        ta++;
        tb++;
    }
}
int main()
{
    ///...
    sort(sa+1, sa+len+1, cmp);
    ///...
}

因为字符串比较的时间复杂度是 $ O(N) $ 的，所以整个算法是时间复杂度是 $ O(n^2logN) $ ，难以接受，所以要寻找更优秀的做法

倍增算法

首先尝试优化字符串比较的时间复杂度，我们可以引入倍增算法。倍增算法的主要思想是进行多轮排序，其中第 k 轮是将所有以每个位置为起点、长度为 $ 2^k $ 的子串进行排序（长度不足则用空字符填充）。其中每个子串都可以拆成两个长度为 $ 2^{k-1}$ 的小子串，他们在上一轮都已经排好序了，所以对原本长度为 $ 2^k $ 的子串排序变成了对 n 个双关键字组合排序。当 $ 2^k >= n $ 时可以看出所有的待排序元素都是原字符串的后缀，所以完成这次排序之后就可以得到正确的 sa 数组

单纯的文字可能难以理解，罗穗骞的论文中有一张形象的图片描述了这个排序的流程

再考虑优化排序的时间复杂度。众所周知，字符串中的字符种类总数是很少的，所以我们可以尝试使用基数排序来实现双关键字排序。我们不妨用一个实例来模拟这个排序的过程。

基数排序

为了说明白基数排序的用法，我们不妨直接上实例。

尝试对以下几个二元组排序

1:{1, 3}   2:{2, 1}   3:{1, 1}   4:{3, 1}

首先我们暂时无视第一维，只对第二维进行计数排序，此时的顺序可能为：

3:{1, 1}   2:{2, 1}   4:{3, 1}   1:{1, 3}

再只针对第一维进行计数排序，因为计数排序是稳定的，所以第一维相同的元素之间第二维的相对有序关系不会发生变化

3:{1, 1}   1:{1, 3}   2:{2, 1}   4:{3, 1}

因为基数排序是 $ O(N*M) $ 的，其中 M 代表字符集大小，可以视为常数，所以采用基数排序的倍增做法整体时间复杂度是 $O(NlogN)$

// s[]:字符串  cnt[]:计数排序计数用   id[] 和 oldrk[] 用于存储临时的旧变量   n:字符串长度  m:字符集大小
void DA(int *s, int *sa, int *rk, int *cnt, int *id, int *oldrk, int n, int m)
{
    int i, p;
    // 初始化数组，也可以理解为对字符排序
    // 这里也用了计数排序，可以理解为求出桶的状态后对桶求前缀和
    // 这样就可以直接求出每个元素排好序之后所在的位置
    // 后面的计数排序也是这个思想
    for(i=1; i<=m; i++) cnt[i] = 0;
    for(i=1; i<=n; i++) cnt[rk[i] = s[i]]++;
    for(i=1; i<=m; i++) cnt[i] += cnt[i-1];
    for(i=n; i>=1; i--) sa[cnt[rk[i]]--] = i;
    for(int w=1; w<n; w<<=1)
    {
        // 先对第二维排序
        memset(cnt, 0, sizeof(cnt)); // cnt数组大小相当于字符集大小，不会太大，所以memset没问题
        for(i=1; i<=n; i++) id[i] = sa[i];
        for(i=1; i<=n; i++) cnt[rk[id[i] + w]]++;
        for(i=1; i<=m; i++) cnt[i] += cnt[i-1];
        for(i=n; i>=1; i--) sa[cnt[rk[id[i] + w]]--] = id[i];
        // 再对第一维排序
        for(i=1; i<=n; i++) id[i] = sa[i];
        for(i=1; i<=n; i++) cnt[rk[id[i]]]++;
        for(i=1; i<=m; i++) cnt[i] += cnt[i-1];
        for(i=n; i>=1; i--) sa[cnt[rk[id[i]]]--] = id[i];
        // 更新 rk 数组
        memcpy(oldrk, rk, sizeof(rk));
        for(p=0, i=1; i<=n; i++)
        {
            if(oldrk[sa[i]] == oldrk[sa[i-1]] && oldrk[sa[i] + w] == oldrk[sa[i-1] + w]) rk[sa[i]] = p; // 判重
            else rk[sa[i]] = ++p;
        }
    }
}

一些优化

也许你看懂了上面这份代码，不要直接用它去当作黑箱，因为他还有很多地方可以进行常数优化

1. 第二关键字无需计数排序

第二关键字在 sa[] 里本来就是有序的，我们只需要把空串放在最前面（无限小），再把那些依旧要参加排序的关键字依序放进去就好了

2. 优化值域

在更新 rk[] 时，我们得到了一个 p ，即为 rk[] 的值域。所以在下一轮我们可以直接把 p 赋值给 m

3. 将 rk[id[i]] 存下来，减少不连续内存访问

4. 把判重部分放进函数中，减少不联系内存访问

5. 若排名都不同（即 p == n） 则则可以直接生成后缀数组

优化后的代码如下

// s[]:字符串  cnt[]:计数排序计数用   id[] 和 oldrk[] 用于存储临时的旧变量   n:字符串长度  m:字符集大小
int cmp(int *oldrk, int x, int y, int w)
{
    return oldrk[x] == oldrk[y] && oldrk[x + w] == oldrk[y + w];
}
// s[]:字符串  cnt[]:计数排序计数用   id[] 和 oldrk[] 用于存储临时的旧变量   px[]:rk[id[i]]   n:字符串长度  m:字符集大小
void DA(int *s, int *sa, int *rk, int *cnt, int *id, int *oldrk, int n, int m)
{
    int i, p;
    // 初始化数组，也可以理解为对字符排序
    // 这里也用了计数排序，可以理解为求出桶的状态后对桶求前缀和
    // 这样就可以直接求出每个元素排好序之后所在的位置
    // 后面的计数排序也是这个思想
    for(i=1; i<=m; i++) cnt[i] = 0;
    for(i=1; i<=n; i++) ++cnt[rk[i] = s[i]];
    for(i=1; i<=m; i++) cnt[i] += cnt[i-1];
    for(i=n; i>=1; i--) sa[cnt[rk[i]]--] = i;
    for(int w=1;; w<<=1, m = p) // m=p即为优化值域 w<n 被省掉是因为有了更好的结束条件
    {
        // 先对第二维排序
        for(p=0, i=n; i>n-w; i--) id[++p] = i; // 先放空串
        for(i=1; i<=n; i++) if(sa[i] > w) id[++p] = sa[i] - w; // 前 w 个子串不会作为第二维参与排序
        // 再对第一维排序
        memset(cnt, 0, sizeof(cnt));
        for(i=1; i<=n; i++) ++cnt[px[i] = rk[id[i]]];
        for(i=1; i<=m; i++) cnt[i] += cnt[i-1];
        for(i=n; i>=1; i--) sa[cnt[px[i]]--] = id[i];
        // 更新 rk 数组
        memcpy(oldrk, rk, sizeof(rk));
        for(p=0, i=1; i<=n; i++)
        {
            rk[sa[i]] = cmp(oldrk, sa[i], sa[i-1], w) ? p : ++p; // 判重
        }
        if(p == n)
        {
            for(i=1; i<=n; i++) sa[rk[i]] = i;
            return;
        }
    }
}

$O(N)$做法

在大多数情况下，出题人不会去卡倍增做法，所以这里不做解释。想要详细了解的同学可以去查阅文末引用的罗穗骞的论文。

题单