首先定义字符串集合上的偏序关系 <

如果 S < T,那么一下情况必定满足且仅满足一个:

  1. \exists i \in [0, \min\{|S|, |T|\}),满足 S(i) < T(i),且 \forall j < iS(j) = T(j)

  2. ST 的一个前缀

后缀排序的排名从 1 开始标号。

简单来讲就是,先看第一个不同的位置,再看长度。

后缀排序要干的事情就是,把某个字符串的所有后缀拿出来,按照上述偏序关系进行排序。我们想要知道每一个后缀是第几大的。

倍增

考虑倍增,对于每个后缀,以其长度为 k = 2^p 的前缀作为关键字进行排序。长度不足 2^k 的后缀,补足空字符(空字符比任何字符都要小)。当 k \geq |S| 时,排序就结束了。

假设我们已经做完了上一轮 k = 2^{p - 1} 时的排序,现在我们想要知道下一轮排序之后的结果。

先做一些定义,方便后续描述(下面描述的都是做完上一轮排序之后的状态,这一轮排序还没有进行)

  • rk[i],第 i 个后缀的排名
  • sa[i],第 i 大的后缀的标号。如果有同样大的,那么视为不同大的(按照某种不确定的方式给这些一样大的后缀标名次)

假设我们要比较两个后缀 i, j 在这一轮中的大小。

本来暴力比较两个字符串的过程就是一位一位比较,但是现在我们已经知道了 \text{substr}(i, i + 2^{p - 1})\text{substr}(j, j + 2^{p - 1})\text{substr}(i + 2^{p - 1}, i + 2^p)\text{substr}(j + 2^{p - 1}, j + 2^p) 的排名(分别就是 rk[i] rk[j] rk[i + k] rk[j + k])。所以我们要做的事情就是,做一次双关键字排序。i 的两个关键字分别为 rk[i], rk[i + k]j 的两个关键字就是 rk[j], rk[j + k]。如果两个后缀的第一个关键字不同,就按第一个关键字排序,否则按第二个关键字排序。

这样做,每次比较 O(1),对所有元素排序的复杂度就是 O(n \log n) 的,总复杂度 O(n\log^2 n)

桶排

可以更快。我们发现这两个关键字的值域都是 [1, n] 中的,所以自然想到桶排。

具体而言,我们称第一个关键字为“十位”,第二关键字为“个位”。这个叫法并非无意而为。

先开 n 个栈,并把每个元素,按照个位塞入对应的栈中,然后再从小到大取出来。这一步实际上就是以个位为关键字进行一次桶排。

接着再开 n 个栈,并把每个元素,按照个位从大到小的顺序,塞入十位对应的栈中,然后再按十位从小到大取出来(每次取出栈顶)。这一步实际上就是以十位为关键字,个位为第二关键字再进行一次桶排。

那么我们在 O(n) 的复杂度内完成了一次排序。

比桶排更简单的做法

这样做常数很大,并且很麻烦,所以我们不直接开 n 个栈。

cnt[i] 表示十位在 [1, i] 的数有多少个。所以我们知道,十位为 i,个位最大的数,排名一定就是 cnt[i]。因此我们先处理出 cnt 数组,按照个位从大到小枚举一个数,然后这个数的排名必定就是他所在的十位的 cnt[],记录 sa[] 之后,将 cnt[] 自减 1。表示下一个比这个数个位小的,十位相同的数,排名减一。

这个做法就比较好写了。

算法流程

总而言之,算法流程如下:

一开始,让所有后缀以 k = 2^0 = 1 排序,i 的十位就是 rk[i] 就是 S(i) 的字符大小。

接着考虑处理 sa[],先计算出所有的 cnt[],由于这一轮中,个位都是相同的(空字符),因此任意顺序枚举一个数,找到十位的 cnt[],记录 sa[]cnt[] 自减。

这就是一开始的情况。

接着是倍增的部分。假设我们枚举到了 k 表示这一轮的长度。实际上还是按照上一段中的做法来做。

首先为了方便,我们引入辅助数组 tp[i] 表示个位第 i 大的后缀的标号。

首先要处理 tp[],首先由于个位是 rk[i + k],对于那些 i + k \geq |S| 的串,他们的个位是全空的,即 tp[] 的前 k 个东西就是这些串。先记录进去。

接着,我们按十位从小到大地枚举一个后缀(就是枚举 sa[] 的一个下标),如果 sa[i] >= k,那么 tp[] 的下一个东西就是 sa[i] - k

处理完 tp[] 后,开始桶排。

先将所有元素,按照十位放进 cnt[],然后做前缀和。接着按照个位从大到小(tp[] 的下标从大到小)枚举一个元素,取出这元素所在的十位的 cnt[] 作为他的 rk。但是 我们并不能这样做,因为这个时候我们还需要用到上一轮 rk(来看这个元素的十位的值),如果还没桶排完就把上一轮的 rk 打乱了,就会出问题。因此我们更新已经不用了的,rk 的逆映射 sa。然后自减 cnt

还有一个小问题,我们刚刚为了方便,桶排的时候更新的是 sark 的逆映射,但是在 sa 中,名次相同的后缀,会被认为名次是不同的。因此我们不能直接把 sa 逆映射回去得到 rk

首先把 rk 拷贝到一个之后不用的数组上面,比如 tp

首先 sa[1]rk 一定是 1,接下来我们正序遍历 sa,如果两个后缀在这一轮排序的排名相同,即两个关键字都相同,所以我们检查一下相邻两个元素的两个关键字是否都相同,是则不移动排名指针,否则要移动。

如果一共有不小于 |S| 个排名,那么就代表着排序可以结束了。

code

const int MAXN = 1e6 + 10;

int N, rk[MAXN << 1], sa[MAXN << 1], tp[MAXN << 1], cnt[MAXN];
char str[MAXN];

void SuffixSort() {
    int m = 128;
    REP(i, N) rk[i] = str[i];
    REP(i, N) cnt[rk[i]]++;
    rep(i, 1, m) cnt[i] += cnt[i - 1];
    REP(i, N) sa[cnt[rk[i]]--] = i;
    for (int k = 1; ; k <<= 1) {
        int p = 0; 
        rep(i, N - k, N) tp[++p] = i;
        REP(i, m + 1) cnt[i] = 0;
        rep(i, 1, N + 1) if (sa[i] >= k) tp[++p] = sa[i] - k;
        REP(i, N) cnt[rk[i]]++;
        rep(i, 1, m + 1) cnt[i] += cnt[i - 1];
        per(i, N + 1, 1) sa[cnt[rk[tp[i]]]--] = tp[i];
        p = 1, swap(tp, rk);
        rk[sa[1]] = 1;
        rep(i, 2, N + 1) rk[sa[i]] = (tp[sa[i - 1]] == tp[sa[i]] && tp[sa[i - 1] + k] == tp[sa[i] + k]) ? p : ++p;
        m = p;
        if (p >= N) return ;
    }
}

特别提醒

  • 记得检查 for 的上下界。字符串的下标从 0 开始,但是排名从 1 开始。
  • 由于根据 sa[]rk[] 里面我们有可能访问 tp[sa[i - 1] + k],为了访问不越界,要开两倍空间。

Height

定义

\text{Height}(i) = |\text{LCP}(\text{Suffix}(\text{sa}(i)), \text{Suffix}(\text{sa}(i - 1)))|

用后缀树来解释就是,dfn 第 i 大的终止节点和第 i - 1 大的节点的 LCA 所代表的子串的长度(深度)。\text{Height}(1) = 0

怎么求?

引理

\text{Height}(\text{rk}(i)) \geq \text{Height}(\text{rk}(i - 1)) - 1,即第 i 个后缀的 \text{Height} 至少为前一个后缀的 \text{Height} 减一。

证明

考虑后缀 i - 1 在 dfn 序上的前驱,记为后缀 j - 1

根据定义 j - 1i - 1 的 LCP 的长度就是 \text{Height}(\text{rk}(i))

如果 j - 1 < |S| - 1,这意味着 j - 1 不是最后一个后缀,那么 j - 1 的下一个后缀 ji - 1 的下一个后缀 i 的 LCP 长度至少为 \text{Height}(\text{rk}(i - 1)) - 1

否则 j - 1 = |S| - 1,即为最后一个后缀,那么 \text{Height}(\text{rk}(i)) = 0 \leq \text{Height}(\text{rk}(i - 1)) - 1

得证。

实现

有了上面这个引理,我们可以在 O(n) 的时间内求出 Height。

考虑枚举一下 i,然后求 \text{Height}(\text{rk}(i))。我们记录上一个 i 的值,然后从上一个 i 的值 -1 开始,暴力匹配后缀 i\text{sa}(\text{rk}(i) - 1)(dfn 序上的前驱)。

\text{Height} 的值减少 n 次,最多不超过 n,因此复杂度 O(n)

int tmp = 0;
REP(i, N) {
    if (tmp) tmp--;
    if (rk[i] == 1) continue;
    while (str[i + tmp] == str[sa[rk[i] - 1] + tmp]) tmp++;
    height[rk[i]] = tmp;
}

OI-字符串 OI-字符串-SA后缀数组

fhq-Treap 速查笔记
上一篇 «
字符串学习笔记总览
» 下一篇