Theme NexT works best with JavaScript enabled

后缀自动机算法探究

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

写在前面

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

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

本文参考:OI-wikiMenci’s BlogWC2012陈立杰后缀自动机讲稿

前置知识及一些概念

后缀自动机,英文名 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;
}

例题解析

咕咕咕咕咕咕咕(

在写了在写了,别骂了别骂了