后缀数组是处理字符串的有力工具。

定义

子串

在字符串 $S$ 中，取任意的 $i \le j$ 并截取 $i$ 到 $j$ 的这一段就叫做 $S$ 的一个子串。

后缀

在字符串 $S$ 中，从某一个位置到字符串末尾的子串叫做其后缀。我们定义从第 $i$ 个位置开始的后缀为 $\text{suffix}(i)$。

后缀数组

后缀数组 $sa(i)$ 是 $1$ 到 $n$ 的一个排列，满足对于所有的 $1 < i \le n$ 都有 $\text{suffix}(sa(i - 1)) < \text{suffix}(sa(i))$。换言之，$sa(i)$ 表示将所有后缀按照字典序从小到大排序后，排名第 $i$ 的后缀为 $\text{suffix}(sa(i))$。

排名数组

排名数组 $rk(i)$ 和后缀数组是互逆的，即满足 $sa(rk(i)) = i, rk(sa(i)) = i$。其实际含义为：$\text{suffix}(i)$ 的在排序后的排名为 $rk(i)$。

思想

如果我们直接对 $n$ 个后缀排序，那么复杂度会高达 $\mathcal O(n ^ 2 \log n)$。这种方法没有利用好 $n$ 个后缀之间的有机关系，而后缀数组就利用这种关系将复杂度优化到 $\mathcal O(n \log n)$。

倍增

倍增算法的主要思路是：我们对所有长度为 $2 ^ k$ 的字符串进行排序，并求出排名（即 $rk(i)$ 数组）。当 $2 ^ k$ 不小于 $n$ 之后，每个位置开始的长度为 $2 ^ k$ 的子串变相当于所有的后缀了，此时的 $rk(i)$ 数组就是答案。

假如当前我们已经把 $2 ^ {k - 1}$ 的子串排好序并求出了排名数组 $rk'(i)$。那么长度为 $2 ^ k$ 的子串可以用两个长度为 $2 ^ {k - 1}$ 的子串的排名作为关键字表示，记为二元组 $(rk'(i), rk'(i + 2 ^ {k - 1}))$；当 $i + 2 ^ {k - 1}$ 时，我们令 $rk'(i + 2 ^ {k - 1})$ 的值为 $0$，因为其对应子串为空串，字典序最小。

得到这些二元组后，我们就可以通过基数排序将长度为 $2 ^ k$ 的子串进行排序，便得到了他们的 $rk(i)$ 值。

基数排序

那么上文所述的基数排序到底怎么实现呢？

我们定义数组 $pos(i)$ 表示第二关键字排名为 $i$ 的后缀为 $\text{suffix}(pos(i))$；用 $bin(i)$ 表示基数排序需要的桶。

现在我们已经得到了长度为 $2 ^ {k - 1}$ 的子串的排名，需要计算长度为 $2 ^ k$ 的子串的排名。

首先用桶统计长度为 $2 ^ {k - 1}$ 的子串的每个排名的出现次数，并对其做前缀和，得到比当前排名小的后缀有多少个。

我们从大到小枚举第二关键字，再用 $rk(i)$ 定位到第一关键字的大小。

那么 $bin(rk(pos(i)))$ 就表示当第一关键字相同时，第二关键字较大的那个后缀的排名。这样我们就有 $sa(bin(rk(pos(i)))) = pos(i)$。

代码

void radixSort() {
    for (int i = 1; i <= m; i++) bin[i] = 0;
    for (int i = 1; i <= n; i++) bin[rk[i]]++;
    for (int i = 1; i <= m; i++) bin[i] += bin[i - 1];
    for (int i = n; i >= 1; i--) sa[bin[rk[tmp[i]]]--] = tmp[i];
}
void build(char *a, int n) {
    m = std::max(n, 255);
    for (int i = 1; i <= n; i++) rk[i] = a[i], tmp[i] = i;
    radixSort();
    for (int l = 1, p = 0; p < n; l <<= 1, m = p) {
        p = 0;
        for (int i = n - l + 1; i <= n; i++) tmp[++p] = i;
        for (int i = 1; i <= n; i++) if (sa[i] > l) tmp[++p] = sa[i] - l;
        radixSort();
        std::swap(rk, tmp);
        p = rk[sa[1]] = 1;
        for (int i = 2; i <= n; i++) {
            rk[sa[i]] = (tmp[sa[i - 1]] == tmp[sa[i]] && tmp[sa[i - 1] + l] == tmp[sa[i] + l]) ? p : ++p;
        }
    }
}

最长公共前缀

注意：前方高能，有大量的证明！请懒得证明的读者直接背结论 QAQ

定义

对于后缀 $\text{suffix}(i)$ 和 $\text{suffix}(j)$，我们定义 $\text{lcp}(i, j) = k$ 其中 $k$ 为满足 $\forall 1 \le p \le k, \text{suffix}(i)_p = \text{suffix}(j)_p$ 的最大值。

接下来再定义一些值：

  • $\text{LCP}(i, j) = \text{lcp}(sa(i), sa(j))$
    即排名为 $i, j$ 的后缀的最长公共前缀。
  • $height(i) = \text{LCP}(i - 1, i)$
    即排名为 $i - 1$ 和 $i$ 的后缀的最长公共前缀。
  • $h(i) = height(rk(i))$
    即 $\text{suffix}(i)$ 与它前一个排名的后缀的最长公共前缀。

我们的最终目的是求解 $height(i)$ 数组。

基本等式

  1. $\text{LCP}(i, j) = \text{LCP}(j, i)$
  2. $\text{LCP}(i, i) = n - sa(i) + 1$

LCP Lemma

在证明接下来的内容之前，我们先证明一个引理

$$ \forall 1 \le i < k < j \le n, \text{LCP}(i, j) = \min(\text{LCP}(i, k), \text{LCP}(k, j)) $$

设 $p = \min(\text{LCP}(i, k), \text{LCP}(k, j))$，那么一定有 $\text{LCP}(i, k) \ge p, \text{LCP}(k, j) \ge p​$。

设 $\text{suffix}(sa(i)) = u, \text{suffix}(sa(k)) = v, \text{suffix}(sa(j)) = w​$，则 $u, v​$ 的前 $p​$ 个字符相等，$v, w​$ 的前 $p​$ 个字符相等。这样得到 $u, w​$ 的前 $p​$ 个字符相等，即 $\text{LCP}(i, j) \ge p​$。

我们考虑反证法，假如 $\text{LCP}(i, j) \ge p + 1$，则有 $u_{p + 1} = w_{p + 1}$，由于排名 $i < k < j$ 那么 $u_{p + 1} = v_{p + 1} = w_{p + 1}$，这与条件矛盾。故 $\text{LCP}(i, j) = p$。

LCP Theorem

在证明好 $\text{LCP Lemma}$ 后，我们可以轻松证明 $\text{LCP}$ 定理：

$$ \forall 1\le i < j \le n, \text{LCP}(i, j) = \min_{i < k \le j} \text{LCP}(k - 1, k) $$

结合引理可以得到：

$$ \text{LCP}(i, j) = \min(\text{LCP}(i, i + 1), \text{LCP}(i + 1, j)) $$

我们将 $\text{LCP}(i + 1, j)$ 可以继续拆下去，正确性显然。

性质

通过上述分析，我们还是没法求 $height$ 数组。于是我们要证明一个最重要的性质：

$$ h(i) \ge h(i - 1) - 1 $$

为了证明这个性质，我们需要明确两个事实：

设 $i, j < n$ 且 $\text{lcp}(i, j) > 1$，那么存在如下事实：

  1. $\text{suffix}(i) < \text{suffix}(j) \Longleftrightarrow \text{suffix}(i + 1) < \text{suffix}(j + 1)$
  2. $\text{lcp}(i + 1, j + 1) = \text{lcp}(i, j) - 1$

接下来尝试证明这个性质。

  • 当 $h(i - 1) \le 1$ 时：

    结论显然成立，因为 $h(i) \ge 0 \ge h(i - 1) - 1$ 肯定成立。

  • 当 $h(i - 1) > 1$ 时：

    将 $h$ 转化为 $height$ 得到 $height(rk(i - 1)) > 1$，由于 $height(1) = 0$（排名为 $1$ 的字符串和空串的 $\text{lcp}$ 显然为 $0$），得到 $rk(i - 1) > 1$。

    令 $j = i - 1, k = sa(rk(j) - 1)$，则显然有 $\text{suffix}(k) < \text{suffix}(j)$，$h(i - 1) > 1$ 等价于 $\text{lcp}(k, j) > 1$。

    根据事实 $1$ 得到 $\text{suffix}(k + 1) < \text{suffix}(j + 1)$ 即 $\text{suffix}(k + 1) < \text{suffix}(i)$，我们用排名数组表示就是：

    $$ rk(k + 1) \le rk(i) - 1 \tag 1 $$

    根据事实 $2​$ 得到：

    $$ \text{lcp}(k + 1, j + 1) = \text{lcp}(k + 1, i) = h(i - 1) - 1 \tag 2 $$

    于是根据 $\text{LCP Theorem}​$ 得到：

    $$ \begin{align*} h(i) & = height(rk(i)) \\ & = \text{LCP}(rk(i) - 1, rk(i)) \\ & \ge \text{LCP}(rk(k + 1), rk(i)) & \text{根据式}\ (1)\\ & = \text{lcp}(k + 1, i) \\ & = h(i - 1) - 1 & \text{根据式}\ (2) \end{align*} $$

    于是最终得到 $h(i) \ge h(i - 1) - 1$，证毕。

代码

for (int i = 1, k = 0; i <= n; i++) {
    k -= (k > 0);
    int j = sa[rk[i] - 1];
    for (; a[i + k] == a[j + k]; k++);
    height[rk[i]] = k;
}

代码

template <int S>
struct SuffixArray {
    static const int N = S << 1;
    int n, m, a[N], sa[N], rk[N], bin[N], tmp[N], height[N];
    void clear() {
        memset(a, 0, sizeof(a));
        memset(sa, 0, sizeof(sa));
        memset(rk, 0, sizeof(rk));
        memset(height, 0, sizeof(height));
    }
    void radixSort() {
        for (int i = 1; i <= m; i++) bin[i] = 0;
        for (int i = 1; i <= n; i++) bin[rk[i]]++;
        for (int i = 1; i <= m; i++) bin[i] += bin[i - 1];
        for (int i = n; i >= 1; i--) sa[bin[rk[tmp[i]]]--] = tmp[i];
    }
    template <class Tp>
    void build(Tp *_a, int _n, int _m) {
        n = _n, m = _m;
        std::copy(_a + 1, _a + n + 1, a + 1);
        for (int i = 1; i <= n; i++) rk[i] = a[i], tmp[i] = i;
        radixSort();
        for (int l = 1, p = 0; p < n; l <<= 1, m = p) {
            p = 0;
            for (int i = n - l + 1; i <= n; i++) tmp[++p] = i;
            for (int i = 1; i <= n; i++) if (sa[i] > l) tmp[++p] = sa[i] - l;
            radixSort();
            std::swap(rk, tmp);
            p = rk[sa[1]] = 1;
            for (int i = 2; i <= n; i++) {
                rk[sa[i]] = (tmp[sa[i - 1]] == tmp[sa[i]] && tmp[sa[i - 1] + l] == tmp[sa[i] + l]) ? p : ++p;
            }
        }
        for (int i = 1, k = 0; i <= n; i++) {
            k -= (k > 0);
            int j = sa[rk[i] - 1];
            for (; a[i + k] == a[j + k]; k++);
            height[rk[i]] = k;
        }
    }
};

习题

最后修改：2019 年 06 月 01 日
© 允许规范转载
如果觉得我的文章对你有用，请随意赞赏