NOI 一轮复习：字符串后缀结构

“后缀 $i$ ” 表示以第 $i$ 个字符开头的后缀。

通常来讲针对字符串子串的问题都会转化到后缀结构上，因为子串有 $O(n^2)$ 个，而所有子串都是某个后缀的前缀，但后缀却只有 $O(n)$ 个。

1. 后缀数组

我们定义 $rk_i$ 表示后缀 $i$ 的排名， $sa_i$ 表示排名为 $i$ 的后缀。

1.1 解法

把所有后缀拿出来，然后暴力排序！

问题是什么？排序本身是 $O(n\log n)$ 次比较的，但是每次比较我们都会重新搞，没利用之前的信息。

假设我们已知 $r_k[i]$ 表示从 $i$ 开始长度为 $k$ 的字符串在所有长度为 $k$ 的子串中的排名，那么我们就可以推得长度为 $2k$ 的子串的排名！

因此实际上是对 $(r_k[i],r_k[i+k])$ 排序：

for (int w = 1; w < n; w <<= 1) {
    // 现在得到 w * 2 时的
    // (rk[x], rk[x + w])
    sort(sa + 1, sa + n + 1, [&](int x, int y) { return rk[x] == rk[y] ? grk(x + w) < grk(y + w) : rk[x] < rk[y]; });
    swap(ork, rk);
    for (int i = 1, p = 0; i <= n; ++i) {
        if (i && ork[sa[i]] == ork[sa[i - 1]] && gork(sa[i] + w) == gork(sa[i - 1] + w)) rk[sa[i]] = p;
        else rk[sa[i]] = ++p;
    }
    if (p == n) break; // 如果已经有了 n 个不同的排名，则已经可以结束
}

我们只需要将其改成两轮计数排序即可变成 $O(n\log n)$ 。即：

for (int w = 1; w < n; w <<= 1) {
    // 现在得到 w * 2 时的 SA
    // (rk[x], rk[x + w])
    for (int i = 0; i <= p + 1; ++i) cnt[i] = 0;
    for (int i = 1; i <= n; ++i) id[i] = sa[i], ++cnt[grk(i + w) + 1];
    for (int i = 1; i <= p + 1; ++i) cnt[i] += cnt[i - 1];
    for (int i = 1; i <= n; ++i) sa[++cnt[grk(id[i] + w)]] = id[i];

    for (int i = 0; i <= p; ++i) cnt[i] = 0;
    for (int i = 1; i <= n; ++i) id[i] = sa[i], ++cnt[rk[i]];
    for (int i = 1; i <= p; ++i) cnt[i] += cnt[i - 1];
    for (int i = 1; i <= n; ++i) sa[++cnt[rk[id[i]] - 1]] = id[i];
    swap(ork, rk);
    p = 0;
    for (int i = 1; i <= n; ++i) {
        if (i && ork[sa[i]] == ork[sa[i - 1]] && gork(sa[i] + w) == gork(sa[i - 1] + w)) rk[sa[i]] = p;
        else rk[sa[i]] = ++p;
    }
    if (p == n) break;
}

另一个优化是发现第一轮计数排序实际上没必要排，直接把上一轮得到的 $sa$ 的后面移到前面（ $i+w>n$ ），剩下的只管这个子串后半部分的排名实际上就是上一轮的排名。但你可以发现这个至多只能优化到原来的 $7/9$ ，而且写这个的时候第一轮开始前的 $sa$ 必须已经是排好序的：

查看代码

#include <bits/stdc++.h>
using namespace std;
constexpr int N = 1e6 + 5;

int n;
char a[N];
/**
 * @brief rk[i] 表示后缀 i 的排名
 * @brief sa[i] 表示排名为 i 的后缀
 */
int rk[N], sa[N], ork[N], id[N], cnt[N];
inline int grk(int x) { return x <= n ? rk[x] : 0; }
inline int gork(int x) { return x <= n ? ork[x] : 0; }

int main(void) {
    ios::sync_with_stdio(false); cin.tie(nullptr);
    // cin >> n >> a;
    cin >> a; n = strlen(a);
    for (int i = n; i >= 1; --i) a[i] = a[i - 1];

    int p = 62;
    for (int i = 1; i <= n; ++i) sa[i] = i, rk[i] = (isdigit(a[i]) ? a[i] - '0' + 1 : ('A' <= a[i] && a[i] <= 'Z' ? a[i] - 'A' + 11 : a[i] - 'a' + 37));
    
    for (int w = 1; w < n; w <<= 1) {
        // 现在需要求得 w * 2 时的 SA
        // (rk[x], rk[x + w])
        // sort(sa + 1, sa + n + 1, [&](int x, int y) { return rk[x] == rk[y] ? grk(x + w) < grk(y + w) : rk[x] < rk[y]; });
        if (w > 1) {
            // 已知的 sa 是 w 时的 sa
            int cur = 0;
            for (int i = n - w + 1; i <= n; ++i) id[++cur] = i;
            for (int i = 1; i <= n; ++i) if (sa[i] > w) id[++cur] = sa[i] - w;
        } else {
            for (int i = 0; i <= p + 1; ++i) cnt[i] = 0;
            for (int i = 1; i <= n; ++i) id[i] = sa[i], ++cnt[grk(i + w) + 1];
            for (int i = 1; i <= p + 1; ++i) cnt[i] += cnt[i - 1];
            for (int i = 1; i <= n; ++i) sa[++cnt[grk(id[i] + w)]] = id[i];
            for (int i = 1; i <= n; ++i) id[i] = sa[i];
        }

        for (int i = 0; i <= p; ++i) cnt[i] = 0;
        for (int i = 1; i <= n; ++i) ++cnt[rk[i]];
        for (int i = 1; i <= p; ++i) cnt[i] += cnt[i - 1];
        for (int i = 1; i <= n; ++i) sa[++cnt[rk[id[i]] - 1]] = id[i];

        swap(ork, rk); p = 0;
        for (int i = 1; i <= n; ++i) {
            if (i && ork[sa[i]] == ork[sa[i - 1]] && gork(sa[i] + w) == gork(sa[i - 1] + w)) rk[sa[i]] = p;
            else rk[sa[i]] = ++p;
        }
        if (p == n) break;
    }
    for (int i = 1; i <= n; ++i) cout << sa[i] << " \n"[i == n];
    return 0;
}

1.2 SA-IS

1.3 height

定义 $ht_i=|\operatorname{LCP}(sa_{i-1},sa_i)|$ 。你当然可以求出 SA 之后二分 + 哈希获得 height 数组，但这成求任意子串的 LCP 了，完全没管 $sa$ 本身的定义。

若 $rk_i<rk_j<rk_k$ ，则 $|\operatorname{LCP}(i,j)|,|\operatorname{LCP}(j,k)|\ge |\operatorname{LCP}(i,k)|$ 。

这好像是一句废话，因为本来就是字典序离得越近 LCP 才可能越长。

假定 $ht_i=|\operatorname{LCP}(sa_i,sa_{i-1})| > 0$ ，则我们去掉两者的第一个字符得到 $ht_i-1=|\operatorname{LCP}(sa_i+1,sa_{i-1}+1)|$ ，换元得到 $ht_i-1=|\operatorname{LCP}(p,q)|$ ，其中 $i=rk(p-1)$ ，且由于第一个字符肯定是相同的所以 $rk_q<rk_p$ ，由之前的废话可知 $rk_q\le rk_z<rk_p$ ，其中满足 $rk_z+1=rk_p$ ，则此时 $|\operatorname{LCP}(p,z)| \ge ht_i-1$ ，而不等式左边就是 $ht_{rk_p}$ 。

因此我们得到了最关键的性质：

$\boxed{ht(rk_p)\ge ht(rk_{p-1})-1}$

直接暴力即可。

ht[1] = 0;
for (int p = 1, k = 0; p <= n; ++p) {
    const int i = rk[p];
    ht[i] = max(0, ht[rk[p - 1]] - 1);
    if (i == 1) continue;
    while (a[sa[i - 1] + ht[i]] == a[p + ht[i]]) ++ht[i];
}

根据那个废话性质可以查询任意两个后缀的 LCP：设 $rk_i<rk_j$ ，则 $|\operatorname{LCP}(i,j)| = \min\limits_{k=rk_i+1}^{rk_j} ht_k$ 。容易证明前者小于等于后者，而由于字典序的连续性，任意两个排名相邻的后缀的前 $|\operatorname{LCP}(i,j)|$ 个字符必定相等。

1.4 本质不同子串个数

模板。

考虑哪些部分是重复的。按照排名依次添加后缀，首先 $ht_i$ 的部分是肯定被数过了，但是再多一个肯定没被数过，因为字典序越临近的 LCP 是越长的，再多一个不会是和之前被统计过的任何一个公共前缀。

1.7 例题

[AHOI2013] 差异

题目。任意两个后缀的 LCP 之和，其实就是把 $ht$ 数组看成矩形的经典单调栈问题。代码。