0xfaner's Blog

Just something trivial

后缀自动机算法探究

Posted on Edited on In
Symbols count in article: 8.4k Reading time ≈ 8 mins.

本文探究了后缀自动机算法及其基础应用

写在前面

后缀自动机在算法竞赛中有着非常重要的地位，它可以在线性时间内解决大多数算法竞赛中常见的字符串问题。

疫情期间，0xfaner 的校队训练也没停下。训练难度陡增，出现了大量诸如后缀自动机这样的高级算法，但是 0xfaner 对许多高级算法只是浅尝辄止，没有尝试过高级应用。导致训练越来越吃力，因此他决定好好梳理一下这些高级算法。

本文参考：OI-wiki，Menci’s Blog，WC2012 陈立杰后缀自动机讲稿

前置知识及一些概念

后缀自动机，英文名 suffix automaton，下文简称 SAM。

要理解 SAM，需要具备字典树（英文名 Trie，下文简称 Trie）和确定有限状态自动机（英文名 DFA，下文简称 DFA）的前置知识。Trie 需要读者自行了解，DFA 在我其他博文中有过介绍。

SAM 的定义

字符串 $s$ 的 SAM 是一个接受 $s$ 的所有后缀的 最小 DFA。

最小是指 SAM 中包含的状态数最少。如果没有这个限制，那么把 $s$ 的所有后缀全部插入到 Trie 中也可以被称为 SAM（时间复杂度和空间复杂度均为 $\mathcal{O}(n^2)$）。

SAM 的优异之处在于，它的构建方法的时间复杂度和空间复杂度均为 $\mathcal{O}(n)$。一个长度为 $n$ 的字符串 $s$ 的 SAM 至多包含 $2n-1$ 个点和 $3n-4$ 条边。$s$ 的所有子串的信息高度压缩在 SAM 中。

虽然 SAM 在定义中是接受 $s$ 的所有后缀，但后来我们也可以用 SAM 来识别 $s$ 的所有子串。

SAM 的结构

SAM 由两部分构成：有向无环单词图（英文名 directed acyclic word graph，以下简称 DAWG）和前缀树（英文名 prefix tree）。

这两部分并不相互独立，它们共用 SAM 中的节点，只是一个是图的形式，一个是树的形式。

下文会讲解结束位置 $endpos$ 的概念来帮助理解 DAWG 的结构。在讲解后缀链接 $link$ 的概念时介绍前缀树。

DAWG 与结束位置 $endpos$

DAWG

DAWG 是 SAM 中最直观的部分，下面给出几个简单字符串的 DAWG 结构以帮助理解，蓝色表示初始状态 $t_0$，绿色表示终止状态（图源：OI-wiki）。

这里需要对 DAWG 进行进一步的说明。

SAM 中的每一个节点代表了 所有从根节点出发到达它的路径 上的字母按顺序连接形成的字符串。

学习 Trie 的同学应该能对这个概念并不陌生。在 Trie 中从根节点出发到达它的路径有且仅有一条。而 SAM 中这个路径可能有多条。

这里就体现出了 SAM 的压缩性质，用一个节点来代表多个不同的子串。压缩的规则会在结束位置 $endpos$ 部分中介绍。下文中会用状态来称呼这些节点。

结束位置 $endpos$

对于字符串 $s$ 的子串 $t$，记 $endpos(t)$ 为 $s$ 中 $t$ 的所有结束位置。

注意这里 $endpos$ 是一个集合，例如：对于字符串 $ABCBC$，有 $endpos(BC)=\{2,4\}$（假设字符串下标从 $0$ 开始）。

根据定义，即使 $s$ 的两个子串 $t_1,t_2$ 不同，$endpos(t_1)$ 仍然有可能和 $endpos(t_2)$ 相同。例如：对于字符串 $ABCBC$，有 $endpos(BC)=endpos(C)=\{2,4\}$。

如果字符串 $s$ 的两个子串 $t_1,t_2$ 满足 $endpos(t_1) = endpos(t_2)$，那么我们认为这两个子串等价。

这样，我们就可以依据 $endpos$ 将 $s$ 的全部子串划分为若干等价类。在 SAM 中，我们用状态来代表这些等价类（也就是 DAWG 和前缀树共用的节点，上文提到过）。

下文中也会用 $endpos(v)$ 来表示状态 $v$ 对应的 $endpos$（同一个状态内的子串的 $endpos$ 都是相等的）。

特别地，记初始状态为 $t_0$。并规定 $endpos(t_0)=\{-1,0,1\dots |s|-1\}$。

那么可以知道 SAM 中状态数等于等价类的数量加一（初始状态 $t_0$ 也是一种）。

这里对 $endpos$ 进行分析，能够得到一些性质。

第一个性质

字符串 $s$ 的两个非空子串 $t_1$ 和 $t_2$ 的 $endpos$ 相同（不妨设 $|t_1|\leq|t_2|$），当且仅当字符串 $t_1$ 在 $s$ 中的每次出现，都以 $t_2$ 后缀的形式存在。

每个 $t_1$ 结束的位置都恰好是 $t_2$ 结束的位置，容易知道 $t_1$ 是 $t _2$ 的后缀。

第二个性质

对于字符串 $s$ 的两个非空子串 $t_1$ 和 $ t_2 $（不妨设 $|t_1|\leq|t_2|$），要么 $endpos(t_1) \cap endpos(t_2) = \phi$，要么 $endpos(t_2) \subset endpos(t_1)$，这取决于 $t_1$ 是不是 $t_2$ 的后缀。

如果 $t_1$ 是 $t_2$ 的后缀，则每一个 $t_2$ 结束的位置都有 $t_1$ 也在此结束。但是 $t_1$ 结束的位置不一定 $t_2$ 也在此结束。所以有 $endpos(t_1) \subset endpos(t_2)$。

如果 $t_1$ 不是 $t_2$ 的后缀，则每一个 $t_1$ 结束的位置，$t_2$ 必定不在这里结束，反之亦然，所以有 $endpos(t_1) \cap endpos(t_2) = \phi$。

第三个性质

对于每一个等价类，将其包含的子串按照长度递增排序，那么排在前面的子串必为排在后面的子串的后缀。且子串的长度恰好覆盖某一个区间中的所有整数。

由第一个性质易证。对于一类等价子串，我们可以用一个区间来描述它们的长度。

例如，对于字符串 $ABCDEBCDEE$，有 $DE, CDE, BCDE$ 等价，长度在区间 $[2,4]$。这三个字符串在 SAM 中将被压缩为同一个状态 $v$。

这里添加几个辅助记号以帮助理解：

  • $longest(v)$ 表示状态 $v$ 所包含的最长子串。

  • $maxlen(v)$ 表示 $longest(v)$ 的长度。

  • $shortest(v)$ 表示状态 $v$ 所包含的最短子串。

  • $minlen(v)$ 表示 $shortest(v)$ 的长度。

于是我们可以用 $[minlen(v),maxlen(v)]$ 来代表状态 $v$ 所包含子串的长度范围。

第四个性质

$endpos$ 集合的之间的包含关系构成一棵树。

由第二个性质可证，把 $endpos$ 相同的子串合并为等价类（状态）后，任意两个状态间的关系要么是无交集，要么一个是另一个的子集。

如果存在状态 $u$ 和状态 $v$ 同时是状态 $t \ (t \neq t_0)$ 的超集，那么 $u \cap v \neq \phi$。根据第二个性质，$u$ 和 $v$ 中的其中一个肯定是另一个的超集。不妨设 $endpos(u)$ 是 $endpos(v)$ 的子集，那么就可以建立 $t \rightarrow u \rightarrow v$ 这样的链。

这样就证明了可以构造出每一个状态最多指向一个状态的树形关系。

第五个性质

$endpos$ 等价类的数量不超过 $2n-1$。

由第四个性质，我们可以根据 $endpos$ 之间的包含关系构造出以 $endpos(t_0)$ 为根的一棵树，子节点是父节点的真子集，兄弟节点之间交集为空集。容易知道这棵树为完全二叉树时子节点最多，为 $2n-1$。

如果无法想象这棵树也没关系，这棵树就是前缀树，可以在看完后缀链接的概念后再来理解。

第六个性质

DAWG 中转移边的数量不超过 $3n-4$。

首先从该 DAWG 中任意提取一棵最长路径生成树，那么该 DAWG 中边即被分为两类：树边与非树边。

树边的数量即为状态数减一，即树边至多有 $2n-2$ 条。

对于字符串的每个后缀，将其输入到 SAM 中都会经过一条终点为接受状态的路径，若经过了一条非树边，则称该后缀对应它经过的 第一条 非树边。注意这里的 第一条，也就是说每一个后缀至多对应一个非树边。

对于每条非树边 $u \rightarrow v$，一定存在一条从起始状态到 $u$ 的不经过任何非树边的路径（因为树上两点间必定有路径），也一定存在一条从 $v$ 到任意一个接受状态的路径（否则依据 DFA 的定义有 $v=null$），所以每一条非树边都对应着至少一个后缀。

因此，非树边数量不会超过后缀数量，且 $s$ 本身必然不经过非树边（因为是最长路径生成树），即非树边至多有 $n-1$ 条。

相加可以得到 DAWG 中边最多有 $3n-3$ 条。

同时我们注意到 $3n-3$ 这个上限是在状态数为 $2n-1$ 时才能达到，但是所有能够使得状态数为 $2n-1$ 的字符串都不能满足边数为 $3n-3$。于是我们得到了更为精确的上界： $3n-4$，由字符串 $abbb\dots bc$ 得到。

前缀树

下面给出字符串 $abcbc$ 对应的 DAWG 的构造与前缀树的构造的对比，对于每一个状态 $v$，我们用 $longest(v)$ 来代表它（图源：OI-wiki）。

前缀树和 DAWG 虽然连边不同，但是所使用的节点是相同的。

DAWG 中的边是字符的转移边，前缀树的边是后缀链接 $link$。

状态 $v$ 的后缀链接指向 $longest(v)$ 的长度为 $minlen(v)-1$ 的后缀所在的状态。

例如，对于字符串 $ABCDEBCDEE$，有 $DE, CDE, BCDE$ 等价，长度在区间 $[2,4]$。这三个字符串在 SAM 中将被压缩为同一个状态 $v$。$longest(v)=BCDE$，$minlen(v)=2$。$longest(v)$ 的长度为 $minlen(v)-1$ 的后缀即为 $E$。

那么状态 $v$ 的后缀链接指向字符串 $E$ 所在的状态 $v’$，记作 $link(v)=v’$。

特别的，当 $minlen(v)=1$ 时，$link(v)=t_0$，$t_0$ 无后缀链接。

这里对 $link$ 进行分析，能够得到一些性质。

第一个性质

所有的后缀链接构成一棵根节点为 $t_0$ 的树。

假定 $link(v)=v’$，那么我们知道 $minlen(v)-1=maxlen(v’)$，即 $maxlen(v)>maxlen(v’)$。所以每个状态最终指向 $maxlen(v)=0$ 的状态，也就是初始状态 $t_0$。

第二个性质

后缀链接构成的树，即为 $endpos$ 集合的包含关系构成的树。

根据 $endpos$ 的第二个性质，我们知道对于任意状态 $v(v \neq t_0)$ 有 $endpos(v) \subsetneq endpos(link(v))$。

并且根据 $link$ 的构造方法，我们知道不存在状态 $u$，使得 $endpos(v) \subsetneq endpos(u)$ 且 $endpos(u) \subsetneq endpos(link(v))$（从 $maxlen$ 和 $minlen$ 的角度来证明）。

那么结合 $endpos$ 的第四个性质的证明，我们知道后缀链接构成的树，即为 $endpos$ 集合的包含关系构成的树。

第三个性质

后缀链接的数量不超过 $2n-2$。

根据第二个性质和 $endpos$ 的第四个性质，除了 $t_0$ 的每一个状态都连出且仅连出一条后缀链接。既然状态数不超过 $2n-1$，那么后缀链接的数量就不超过 $2n-2$（除去 $t_0$）。

算法策略及代码实现

SAM 的构造是一个增量算法，假定我们已经有了字符串 $s$ 的长度为 $i$ 的前缀对应的 SAM，我们就可以均摊 $\mathcal{O}(1)$ 地构造 $s$ 的长度为 $i+1$ 的前缀对应的 SAM。

现在详细地阐述如何进行这一过程，在此之前要进行一些约定并说明性质。

一些约定与性质

约定

做出一些约定，以避免歧义并使得陈述更加简短。

  • 目的是构建字符串 $S$ 对应的 SAM ；

  • 当前已经有了字符串 $s$ 的 SAM ；

  • 接下来要添加一个字符 $x$，使得该 SAM 变为 $s+x$ 对应的字符串。

  • 用 $s’$ 表示新字符串 $s+x$。

  • $last$ 表示字符串 $s$ 对应的节点。

  • 后缀链 $links(t_1,t_2)$ 表示从状态 $t_1$ 或字符串 $t_1$ 所对应的节点开始，沿着后缀链接一直向上追溯到状态 $t_2$ 或字符串 $t_2$ 的链。

性质

添加一个字符 $c$，等价于向 SAM 中插入字符串 $s+c$ 的所有后缀。

要添加的后缀分为两类：

  1. 该后缀是字符串 $s$ 的子串，即原 SAM 中已经包括该后缀，插入会使得该后缀的 $endpos$ 变化。

  2. 该后缀不是字符串 $s$ 的子串，即原 SAM 中不包括该后缀，插入会使得 SAM 中新增节点。

例如对于字符串 $ABC$，我们插入一个字符 $C$，字符串变为 $ABCC$。相当于插入四个后缀 $ABCC$ , $BCC$ , $CC$ , $C$。其中 $ABCC$ , $BCC$ , $CC$ 是新增的后缀，这些新增的后缀同属一个新增的等价类，$endpos=\{3\}$ ; $C$ 是已有的后缀，$endpos(C)$ 从 $\{2\}$ 变为 $\{2,3\}$。

取 $s$ 的全部后缀以及一个空串，在它们末尾加入字符 $c$ 即可得到字符串 $s’$ 的全部后缀。而字符串 $s$ 的全部后缀恰分布在 $links(s,t_0)$ 上。所以只需要在 $links(s,t_0)$ 上进行分析比对即可。

下面对两类后缀进行性质分析。用 已有后缀 和 新增后缀 来分别称呼它们，用 待添加后缀 来称呼它们中的某一个，用 对应后缀节点 来称呼某一个待添加后缀删除末尾的字符 $x$ 后的字符串对应的节点。

对待添加后缀进行分析，可以得到一些性质：

第一个性质

已有后缀不一定存在，而新增后缀必定存在，且所有的新增后缀同属一个等价类。

例如，当 $s$ 是空串时已有后缀就不存在，而新增后缀最起码有单个字符 $x$ 代表的的字符串。

所有的新增后缀都只在当前字符 $x$ 处结束，所以它们的 $endpos$ 是相同的，自然同属一个等价类。

第二个性质

新增后缀的长度均大于已有后缀的长度。

从定义出发即可，假定一个待添加后缀 $t$ 是一个已有后缀，那么所有长度小于 $t$ 的待添加后缀均为已有后缀。

第三个性质

已有后缀的对应后缀节点存在字符 $x$ 的转移边，而新增后缀则不存在。

已有后缀存在于原 SAM 中，那么它的对应后缀节点必然会存在指向它的字符 $x$ 的转移边。

这将成为代码中判别一个待添加后缀是否是已有后缀的方法。

算法策略

结合上面的性质进行算法策略的讨论。

记新增后缀的节点为 $np$。

根据第一个性质，新增后缀必定存在，且同属一个等价类，我们用一个节点 $np$ 来代表它。

记从节点 $last$ 出发，找到的第一个存在字符 $x$ 的转出边的节点为 $p$。

根据第三个性质，我们知道 $p$ 为已有后缀的节点。而根据第一个性质，已有后缀可能不存在，所以 $p$ 可能不存在。下面对其分类讨论。

$p$ 不存在

这是最简单的情况，这种情况下所有的待添加后缀均为新增后缀。

那么直接让 $links(last,t_0)$ 上的节点全部对 $s$ 连出一个字符 $x$ 的转出边到 $np$，同时令 $links(np)=t_0$ 即可。

$p$ 存在

记 $p$ 的沿着字符 $x$ 转移到达的节点为 $q$。

结合第二个性质和第三个性质，我们知道 $links(p,t_0)$ 上的节点恰为全部已有后缀的对应后缀节点，所以 $links(q,t_0)$ 上的节点恰为全部已有后缀。这些已有后缀的 $endpos$ 会增加一个在当前字符 $x$ 处结束的位置。

这里也要注意到有可能 $q$ 中所有的字符串并非都是由节点 $p$ 转移得到的，这样 $q$ 中就只有较短那一部分子串的 $endpos$ 才会变化，所有要把 $q$ 拆分为两个节点。

这里判别 $q$ 中的字符串是否均由 $p$ 转移得到，可以比较 $maxlen(q)$ 是否等于 $maxlen(p)+1$。

下面对其分类讨论：

$maxlen(q)=maxlen(p)+1$

这种情况下，$q$ 中的字符串均由 $p$ 转移得到，我们无需对 $q$ 进行拆分。

那么问题就简单的分为处理新增后缀和已有后缀。

对于新增后缀，直接让 $links(last,p)$ 上的节点全部对 $s$ 连出一个字符 $x$ 的转出边到 $np$，同时令 $links(np)=q$ 即可。

对于已有后缀，我们甚至无需处理，因为虽然 $endpos$ 改变了，但实际代码中并没有存储 $endpos$。

$maxlen(q) \neq maxlen(p)+1$

这种情况下，$q$ 中的字符串并非均由 $p$ 转移得到，我们需要对 $q$ 进行拆分。

实际代码中并未存储 $endpos$ 等信息，只需存储每个节点的转移边、 $maxlen$ 和 $link$，我们拆分节点也只需要对这三个变量进行修改即可。

令拆分出的节点为 $nq$。

第一，要进行转移边的复制，即将 $ch[q]$ 赋值给 $ch[nq]$ 即可；

第二，$nq$ 的后缀链接要复制 $q$ 的后缀链接，即 $link[nq]=link[q]$ ；

第三，$q$ 的后缀链接要重新指向 $nq$，即 $link[q]=nq$ ；

第四，$manlen(nq)$ 要变为 $maxlen(p)-1$ ；

第五，将其他点到 $q$ 的转移边指向 $nq$，即将 $links(p,t_0)$ 上的节点的字符 $x$ 的转移边重新指向到 $nq$。

这样我们就完成了拆分，问题只剩下处理新增后缀。

对于新增后缀，直接让 $links(last,p)$ 上的节点全部对 $s$ 连出一个字符 $x$ 的转出边到 $np$，同时令 $link(np)=nq$ 即可。

至此我们就完成了全部情况的讨论，明确了每一步的操作，以及代码中全部变量的含义。

名词补充

国内外的 SAM 的部分概念采用了不同的名称，为避免歧义，这里单独说明下。

  • $endpos$ 集合对应 $right$ 集合

  • 前缀树对应 $parent$ 树

在代码中，也有多种不同的变量名：

  • 转移边：一般有 ch , nxt ( next ) , trans

  • 接收状态（识别状态、结束状态）： occor , reg

  • 后缀链接： link , parent

  • 最长等价串： maxlen , len

代码实现

以 Luogu P3804【模板】后缀自动机 (SAM) 为例：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
#include <bits/stdc++.h>
using namespace std;
#define N 2000010
#define ll long long
int last, num;
int ch[N][26], link[N], occur[N], maxlen[N];
void extend(int x) {
    int p = last, np = last = ++num;
    maxlen[np] = maxlen[p] + 1, occur[np] = 1;
    while (p && !ch[p][x]) ch[p][x] = np, p = link[p];
    if (!p)
        link[np] = 1;
    else {
        int q = ch[p][x];
        if (maxlen[q] == maxlen[p] + 1)
            link[np] = q;
        else {
            int nq = ++num;
            memcpy(ch[nq], ch[q], sizeof ch[nq]);
            link[nq] = link[q], link[q] = link[np] = nq;
            maxlen[nq] = maxlen[p] + 1;
            while (p && ch[p][x] == q) ch[p][x] = nq, p = link[p];
        }
    }
}
char s[N];
int t[N], A[N];
int main() {
    last = num = 1;
    scanf("%s", s + 1);
    int len = strlen(s + 1);
    for (int i = 1; i <= len; i++) extend(s[i] - 'a');
    for (int i = 1; i <= num; i++) t[maxlen[i]]++;
    for (int i = 1; i <= num; i++) t[i] += t[i - 1];
    for (int i = 1; i <= num; i++) A[t[maxlen[i]]--] = i;
    ll ans = 0;
    for (int i = num; i; i--) {
        int add = A[i];
        occur[link[add]] += occur[add];
        if (occur[add] > 1) ans = max(ans, (ll)occur[add] * maxlen[add]);
    }
    printf("%lld\n", ans);
    return 0;
}

例题解析

咕咕咕咕咕咕咕（

在写了在写了，别骂了别骂了