前言

不能完全不管字符串，就硬着头皮学一学。

完全未完工。

后缀数组

后缀数组主要指的是两个数组：

$sa_i$ 表示排名第 $i$ 小的后缀的起始位置；

$rk_i$ 表示从 $i$ 开始的后缀的排名。

这里的后缀大小比较的是字典序。

说白了以上两个数组的意思分别是 kth 和 rank。

很显然 $sa_{rk_i}=rk_{sa_i}=i$

建议好好记住这个定义，否则以后可能绕来绕去就糊涂了。

后缀数组求法

不讲线性求法了（我也不会），我们来说一说常见好写的倍增法。

我们不是要求 $sa$ 吗，显然有 $sa$ 数组中两个下标 $i<j$ 的条件是 $rk_{sa_i}<rk_{sa_j}$。

假设我们对从每个字符开始长度为 $w$ 的串排好序了。

然后我们试图得到长度为 $2w$ 的 $sa$ 数组。

我们只需要把 $sa$ 数组以 $rk_{i}$ 为第一关键字，$rk_{i+w}$ 为第二关键字排序就行了。得出 $sa$ 数组之后再更新一下 $rk$ 数组即可。

听起来很简单啊，算一下复杂度，如果用快速排序，时间复杂度是 $O(n\log^2n)$ 的。

但是！如果我们用基数排序而不是快速排序，时间复杂度会优化到 $O(n\log n)$。

这个基数排序就是万恶之源了。

啥是基数排序呢？就是对于多关键字的排序，先对第二关键字稳定排序，再对第一关键字稳定排序，就能对整个序列稳定排序。

然后如果对每个关键字排序时使用计数排序，复杂度是 $O(n)$，那么在求 SA 的时候排序复杂度也就是 $O(n)$ 了。

然后就是比较绕的地方了，如果头脑很困不清醒（比如我）可能就会被绕进去。

计数排序的原理说白了也很简单：算出比每个值小（或者说优先级更高）的值有几个，然后把这个值放到正确的位置里。

在这里我们需要计数的是 $rk$ 的值。

emmmm好像没什么可以说的了，该看代码理解了。

借用 OI Wiki 上的一份代码：

#include <algorithm>
#include <cstdio>
#include <cstring>
#include <iostream>

using namespace std;

const int N = 1000010;

char s[N];
int n, sa[N], rk[N << 1], oldrk[N << 1], id[N], cnt[N];

int main() {
  int i, m, p, w;

  scanf("%s", s + 1);
  n = strlen(s + 1);
  m = max(n, 300);
  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 (w = 1; w < n; w <<= 1) {
    memset(cnt, 0, sizeof(cnt));
    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]; // 对第二关键字进行计数排序
    memset(cnt, 0, sizeof(cnt));
    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]; // 对第一关键字进行计数排序
    memcpy(oldrk, rk, sizeof(rk));
    for (p = 0, i = 1; i <= n; ++i) { // 更新 rk 数组时需要注意：完全相同的串排名也应该一样。
      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;
      }
    }
  }

  for (i = 1; i <= n; ++i) printf("%d ", sa[i]);

  return 0;
}

然后上面的代码常数是很大的。

有以下的常数优化：

  • 第二关键字无需计数排序，只需把超过范围的放到前面，剩下的按照原先顺序填进去即可。
  • 优化值域：每次计数排序的值域可以设为每一次更新 $rk$ 时不同元素的个数。
  • 用一个数组存下来 $rk_{id_i}$：减少不连续内存访问（我的盲区）。
  • 用函数 cmp 来计算是否重复：减少不连续内存访问（我的盲区）。
  • 若排名都不相同可直接生成后缀数组：如果 $rk$ 的值域已经达到了 $[1,n]$，那么已经排好序，无需接着生成数组。

下面是我写的优化过常数的代码：

#include <algorithm>
#include <cstdio>
#include <cstring>
#include <iostream>
using std::cerr;
using std::cin;
using std::cout;
using std::endl;

const int maxn = 1e6 + 10;

char s[maxn];

int n, p, sa[maxn], rk[maxn << 1], tmp[maxn], cnt[maxn], oldrk[maxn << 1], val[maxn];

inline bool equ(int i, int j, int dep) { return oldrk[i] == oldrk[j] && oldrk[i + dep] == oldrk[j + dep]; }

int main()
{
    scanf("%s", s + 1);
    n = strlen(s + 1);
    int m = 300, p;
    for (int i = 1; i <= n; i++)
        cnt[rk[i] = s[i]]++;
    for (int i = 1; i <= m; i++)
        cnt[i] += cnt[i - 1];
    for (int i = n; i >= 1; i--)
        sa[cnt[rk[i]]--] = i;
    for (int dep = 1; dep <= n; dep <<= 1, m = p)
    {
        p = 0;
        for (int i = n - dep + 1; i <= n; i++) // 把超过去的放到前面
            val[++p] = i;
        for (int i = 1; i <= n; i++) // 剩下的按照原顺序填进去
            if (sa[i] > dep)
                val[++p] = sa[i] - dep;
       	// val 是按照第二关键字排序后的 sa 数组的值
        memset(cnt, 0, sizeof(cnt));
        for (int i = 1; i <= n; i++)
            cnt[tmp[i] = rk[val[i]]]++; // tmp 是常数优化用的
        for (int i = 1; i <= m; i++)
            cnt[i] += cnt[i - 1]; // 对计数排序用的数组求前缀和来得到元素的位置
        for (int i = n; i >= 1; i--)
            sa[cnt[tmp[i]]--] = val[i]; // 对于排序前数组的每个值分配一个新位置
        std::swap(rk, oldrk);
        p = 0;
        for (int i = 1; i <= n; i++)
            rk[sa[i]] = equ(sa[i], sa[i - 1], dep) ? p : ++p; // 更新 rk 数组
        if (p == n) // 最后一个优化
            break;
    }
    for (int i = 1; i <= n; i++)
        printf("%d ", sa[i]);
    return 0;
}

应用

咕咕咕