后缀自动机（SAM）学习笔记

· · 算法·理论

后缀自动机（SAM）学习笔记

前言

如读者们所见，可以看到我的专栏中从来没有过学习笔记，这是第一次。

写这一篇学习笔记的原因是，我真的觉得，后缀自动机是我学 OI 以来最抽象最难理解的东西。

所以我将用很多图片和具体的描述来解释这一抽象的数据结构，用于自己参考回顾，同时方便读者学习。

后缀自动机强势图解

需要的前置知识：Trie 树（字典树），基本字符串知识，基本集合知识，图论基础。

声明：不要跳过任何部分，哪怕你认为你明白这部分，否则可能阅读到的信息不连续导致不懂。

如果下文的图挂了请联系我或者评论。

正文部分来啦，我们首先需要相信它很简单，不能被敌人吓趴了。

01. 自动机

自动机用于对一个信号序列进行判定。

OI 界指的自动机一般是确定有限状态自动机（缩写是 DFA），即转移方案确定且状态有限。

我们通常用一个有向图来描述自动机，以节点描述状态，以有向边来描述状态之间的转移。

下图描述了一个自动机：

我们令 1 号节点为开始节点（即接收的信号从这里开始转移）。

当我们接收到一个 b 字符，上图自动机会转移到 4 号节点。

如果我们此时在 4 号节点接收到信号 c 就会转移到 5 号节点，如果信号中止了，这时我们称 5 号节点为结束节点。

如果我们此时在 4 号节点接收到信号 a 怎么办呢？

这代表着上图的自动机并不接受 ba 的信号（a 之前的 b 是从 1 号节点转移到 4 号节点的 b）。

02. 后缀自动机的引入

一个 DFA，它能接受一个字符串的所有子串。

SAM（Suffix Automaton，后缀自动机）是满足该条件的节点数最少的 DFA。

在下文中可以证明，SAM 的节点个数至多为 2n-1，边数至多为 3n-4（点数的证明在【用后缀树的角度构建】那里，边数的放文章最后）。

举个例子，下面图片是 aabab 的后缀自动机：

我们令 1 号节点为开始节点，比如接收到信号 aba，上图后缀自动机的转移是这样的：1\to2\to7\to5。

当我们接收到不合法的信号比如 bb，上图后缀自动机是转移不了的（注意是有向边）。

大家可以试试其他 aabab 的子串，都可以表示；反之，不是 aabab 的子串都不能表示。

引入 1.【后缀树】

有的资料以 parent 树引入，注意，它们不是同一个东西。（事实上，反串的 parent 树就是原串的后缀树。）

在本文中我们以后缀树作为 SAM 的引入，不再提及 parent 树。我个人认为以后缀树作为引入会比 parent 树直观、好理解很多。

后缀树是这样的：

比如对于字符串 ababc，其所有后缀拿出来建立的 Trie 树如下图所示：

注意到节点数过多，还注意到只有红色节点的出度大于 1，我们称红色节点为“端点”，我们可以这样操作：

这就是 ababc 的后缀树了（注意按照顺序从左往右读，不要被边的方向弄混了）。

除特殊说明外，下文的后缀树都是指压缩路径（虚树）后的后缀树。

先记着这个，后面要用。

引入 2.【endpos 集合】

举个例子：

对于字符串 ababc，其子串 ab 的 endpos 集合为 \{2,4\}（以 1 开始编号）。

注意到 endpos 有个性质：对于任意两个原串的子串 s1,s2，若 s1 是 s2 的后缀，则 endpos_{s2}\subset endpos_{s1}。

我们还能注意到：

  1. 两个 endpos 集合不同的串不可能共享 SAM 上的同一个节点，否则转移是不确定的；
  2. SAM 会保证任意两个 endpos 集合相同的串共享一个节点，因此 SAM 的节点数（状态数）是最少的。

简单来说，就是可行的（存在的） endpos 集合与 SAM 上的节点形成了双射。这一点后面要用，请留意。

我们让 SAM 的每一个节点表示一个 endpos 集合。

比如我们拿出上文 aabab 的 SAM（在【02. 后缀自动机的引入】那个章节里），并且标上每个节点的 endpos 集合。

我们可以发现：

无论我们走 1\to7\to5（得到 ba），还是走 1\to2\to7\to5（得到 aba），或者走 1\to2\to3\to4\to5（得到 aaba），

它们所对应的子串（ba、aba 和 aaba）的 endpos 集合都是 \{4\}，并且只共享了一个结束节点 5，这样的 SAM 的节点数一定是最少的。

03. 后缀自动机的构建

我们需要在 O(n) 内构造后缀自动机。

讲完了后缀自动机的概念和一些辅助的东西（endpos 和后缀树），它那么可爱，应该如何构建呢？

后缀树、endpos 集合与 SAM 之间的联系

我们考虑构建一个串的反串的后缀树。

举个例子，比如有一个串是 cbaba，它的反串是 ababc，构建 ababc 的后缀树。

我们在上文已经构建好了（见【引入 1】）：

后缀树是把一个串的所有后缀拿出建 trie 树，然后再压缩。

我们对反串建后缀树，是拿出反串的后缀建 trie 后压缩，这等价于拿出原串的前缀反着建 trie 后压缩。

比如 cbaba，拿出前缀 c、cb、cba、cbab、cbaba。

然后反着建 trie（即把所有的前缀的反串放进 trie 中）。

也就是往 trie 中分别加入 c、bc、abc、babc、ababc。

有点抽象是吧，看图：

我们把其对应的后缀树拿过来放在一起看，以上图第三行为例，当我们反着加入 cba 的时候（即 abc），对应后缀树这样一条路径（红色）：

注意到这一条路径是到叶子结点的。

我们发现一个第三行的 abc 的反串（即 cba，也即原串的前缀）在原串 cbaba 上的 endpos 集合为 \{3\}。

说明上图后缀树的 12 节点代表的 endpos 集合为 \{3\}。

同样的，我们可以发现第五行反串 cbaba 的 endpos 集合为 \{5\}，也即后缀树上 6 节点 endpos 集合为 \{5\}，第一行第二行第四行都是一样的。

我们就得到了下图：

进一步的，如果我们按照后缀树上的边走，得到的串的反串（即原串的前缀），在原串的 endpos 集合为下图：

注意我们强行规定空串的 endpos 集合为所有位置（即上图 1 节点）。

这时我们发现一个惊人的事实：叶子结点的 endpos 集合大小为 1，非叶子节点的 endpos 集合为其儿子 endpos 集合的并集（事实上并集这个东西可以在【引入 2】那里得到理性证明，就是那张写了 endpos 性质的图）。

所以两个相同的 endpos 集合不会用两个点表示，同时同一个点也不会表示两个不同的 endpos 集合。

这说明 endpos 集合与反串的后缀树的节点也形成了双射！

前面我们证明过了 endpos 集合与 SAM 的节点形成了双射（在【引入 2】那里，原谅我没有用相同的串举例）。

这说明：

SAM 节点、endpos 集合相同的串、反串的后缀树节点，三者一一对应！

尽管我没有用相同的串举例，但是读者们可以去画一画，会发现确实是这样的。

这说明，我么可以利用后缀树来帮助构建 SAM，因为其节点是一一对应的。

从后缀树的角度构建

接下来可能不能用具体的例子了，请读者们做到全神贯注（真的很难讲懂这个东西啊）。

请注意，区别于上文，下文的后缀树的树边我们将用无向边。

我们假设已经构建了原有的字符串的后缀树，长这个样子：

我们构建 SAM，是在原有字符串的末尾添加一个字符。

这相当于新添加一个原串的前缀的反串，如图所示：

这在后缀树上表现为添加一条从根节点开始的链：

注意后缀树本质上是 trie 树，所以新加链，可能会存在一段相同的路径，之后再分叉，如上图。

在链中间新加节点是因为后缀树是压缩的 trie，压缩后原有节点可能不能满足新的链的需要。

当然也不一定是这样的，不仅有上图情况，也有可能有以下情况：

不管怎么样，总之新添加的节点个数一定 \le 2。

由于后缀树上节点与 SAM 上一一对应，这也证明了 SAM 的节点个数是 2n 级别的，事实上是 2n-1，证明如下：

SAM 最初有 1 个初始节点，后面添加的 2 个字符都只新增 1 个节点，最后 n-2 个字符新增至多 2 节点，所以节点个数上限为 3+2(n-2)=2n-1。

构建真正的 SAM

铺垫了这么久，终于来了！

事实上 SAM 和反串的后缀树是同步构建的。为了在加入新字符的时候构建出新的 SAM，其反串的后缀树也是要维护的。

换句话说，我们需要的 SAM 实际上就是在后缀树上加转移边！！！

而后缀树上的树边并不是 SAM 的边，但后缀树上的点是 SAM 的点。

再说一遍，后缀树和 SAM 是共用节点的！！！

我们规定后缀树上儿子指向父亲的边叫做 SAM 的 link（中文名叫做后缀链接）。

假设下图是一个 SAM，下图红色的有向边叫做 link。

注意注意注意！！！

  1. 注意区分树边（后缀树上无向边）、link（SAM 上指向父亲的链接，不是边）和转移边（SAM 收到信号的转移的有向边）、fa（后缀树上节点的父亲），这很重要，容易混！
  2. 注意区分下文表述的是后缀树还是 SAM，这也很重要，容易混！
  3. 由于 SAM 与后缀树共用点不共用边，除特殊说明外，凡是 SAM 的转移边我都用粉色，其余的要么是树边，要么是 link，但 link 我会画出方向，以便区分。

后缀树压缩前的平行关系

好的，我们继续。

每个 SAM 上的节点的 link 是唯一的，除了根节点没有。

我们可以发现，在未被压缩的后缀树上（即不进行取虚树操作的 trie 上），SAM 的转移边构成了平行关系。

什么意思呢？假设我们有一个字符串 s_1s_2s_3\dots s_{n-1}s_n，画出它的反串在未压缩后缀树上的路径（其余边未画出）：

假设我们现在添加一个字符 c，变成 s_1s_2s_3\dots s_{n-1}s_nc，可能形成的未压缩后缀树如下（若 c 和 s_n 相同就不是这种情况，但同理）：

我们可以观察到，最下面的两个叶子结点，经过后缀树的根节点走过来，组成了 cs_ns_{n-1}\dots s_1 和 s_ns_{n-1}\dots s_1。

我们称在 SAM 中，这两个节点代表了 s_1s_2s_3\dots s_{n-1}s_nc 和 s_1s_2s_3\dots s_{n-1}s_n 这两个字符串（注意，后缀树是反串）。

换句话说，SAM 中每个节点代表了其后缀树上从根节点走过来的字符串的反串。

此时这个 SAM 需要转移边，下图是 SAM 新添的转移边：

表示了从代表 s_1s_2s_3\dots s_{n-1}s_n 的节点，经过了一条 c 的转移边，可以到达代表 s_1s_2s_3\dots s_{n-1}s_nc 的节点。

同理的，需要更多的转移边（忘记画根节点的转移了抱歉）：

这些转移边表示了：从代表 s_is_{i+1}\dots s_{n-1}s_n 的节点，经过了一条 c 的转移边，可以到达代表 s_is_{i+1}\dots s_{n-1}s_nc 的节点。

是不是平行的？这就是所谓的平行关系。

我们可以得到以下性质：

当然，在压缩过的后缀树上也会有这样的平行关系，只不过因为被我们压缩了，所以长得很奇怪。

后缀树压缩后的平行关系

接下来讲压缩过后的。

重复一遍上文，在未经压缩的后缀树对应的 SAM 中，称一个节点代表其后缀树从根节点走过来的字符串的反串。

在 SAM 中，若其后缀树被压缩了，那么称这个节点代表：其后缀树从根节点开始，走到其后缀树的这个节点的父亲，与当前节点与其父亲的树边上的字符，所组成的字符串反串组。

很抽象是吧，其实不难理解：

左边的 6 号节点代表 cbaba（反串），右边的 6 号节点代表以下字符串组：

不理解的可以结合图多看几遍。

然后以字符串 cbaba 为例，根据每个节点代表的内容，压缩后的平行关系如下图所示（只是可能的示意图，并不代表一定长这个样子）：

可以发现，由于被压缩了，本来应该转移到后缀树树边上的 SAM 转移边，实际上转移到了其下方的点。

如何构建

接下来，我们称一个节点代表一个字符串，当且仅当其代表的字符串组中有这个字符串。

我们假设已经建好了原有串的后缀树：

我们需要维护一个 las，表示当前代表原串的节点。

假设有一个字符串 s_1s_2\dots s_n。

下图绿色的路径就是 s_ns_{n-1}\dots s_1。

现在我们加入一个字符 c，相当于往后缀树中加入了 cs_ns_{n-1}\dots s_1 这一条路径。

有可能长这个样子：

我们考虑这之后 SAM 应该有的转移边可能是什么（注意此处不是粉色，而是红色）：

但是由于后缀树被压缩了，实际上 SAM 是这个样子的（我们假设 2 号节点已经有 c 的转移边了）：

于是我们得到一个初步的流程：

  1. 新建节点 cur（上图为节点 7）。
  2. 如果 las 没有 c 的转移边，将 las 往 cur 连一条 c 的转移边。
  3. 让 las\gets link_{las}（这是赋值符号，下同），即跳后缀链接（也即走到其后缀树上的父亲）。
  4. 重复 2,3 操作，直到发现是根节点或者有 c 的转移边。

为什么可以“找到有 c 边”就结束呢？因为如果这个点有 c 边，根据平行关系，其后缀树上父亲也有 c 边，往上一直有 c 边，就不用操作了。

此时我们把没有 c 的转移边的节点都向 cur 连了 c 边。

考虑接下来怎么做，具体的，我们要考虑怎么把 cur 接到原树中去。

我们考虑上一个流程结束后，有 c 的转移边的那个点（图中为 2 号点）转移到的点。

有两种可能的情况（第二种就是我们刚刚举的例子）：

此时 2 号点原本有的 c 边如下图所示：

我们令上图 2 号点为 p，通过其 c 转移边转移到的点叫做 q。

解释一下为什么第二幅图 q 是 6 号节点：它应该在 8 号节点，由于被压缩了，我们上文讲过了（在【后缀树压缩后的平行关系】那里），实际上它连的转移边是其下面的点。

然后第一种情况很好解决，直接 link_{cur}\gets q 就把 cur 接到原树中了。

考虑第二种情况，我们从最开始什么都没有来讲（注意黑色边的定义改成了 link）：

新建节点 cl，图中是 8 号节点。

然后让 link_{cl}\gets link_q。

此时把所有 q 的转移边直接给 cl（图中未画出）。

然后 link_{cur}\gets cl，link_{q}\gets cl。

这样就把 cur 正确地接进树中了，是不是很像链表？但是我们还要考虑转移边。

我们上文讲过平行关系，即 p 及以上的节点都有 c 边，我们要把这些指向 q 的 c 边全部改成指向 cl，暴力跳 link 即可（至于复杂度为什么正确，文章最后见）。

这样就在原 SAM 基础上构建完新 SAM 了。

现在还有一个很重要的问题，怎么判断是第一种情况还是第二种？

我们考虑每个节点维护一个 len，表示这个节点在 SAM 上代表的字符串的最大长度（还记得什么是“代表”吗？在【后缀树压缩后的平行关系】那里）。

我们考虑 q 的 len 应该是多少。是不是应该是 len_p+1（因为我们走了一条转移边）？

所以我们只需要判断 len_q=len_p+1，若成立，就是第一种情况，否则就是第二种情况。

然后如果是第二种情况，还要在新建节点的时候 len_{cl}\gets len_p+1。

注意刚开始的 cur 的 len 也要维护。就没了。剩下的看代码吧，有注释。

04. 构建 SAM 代码

说了那么复杂，实际上代码超级短。

struct SAM
{
    struct node{int len,lk;int e[26];}nd[N<<1]; // 每个节点维护 len、link、还有其转移边（字符集大小）
    int cnt=1,las=1; // SAM 初始要有一个节点，表示空串
    void insert(int c)
    {
        int cur=++cnt; // 新建 cur
        nd[cur].len=nd[las].len+1; // 更新 cur 的 len
        for(;las&&!nd[las].e[c];las=nd[las].lk)nd[las].e[c]=cur; // 不断跳 link，把 c 边都指向 cur，直到找到有 c 边的节点
        if(!las)nd[cur].lk=1; // 如果根本找不到有 c 边的节点，直接将 cur 的 link 赋值为根节点编号即可
        else
        {
            int p=las,q=nd[las].e[c]; // 与上文意义相同的 p,q
            if(nd[q].len==nd[p].len+1)nd[cur].lk=q; // 第一种情况
            else // 第二种情况
            {
                int cl=++cnt; // 新建 cl
                nd[cl].lk=nd[q].lk,nd[cl].len=nd[p].len+1; // 与上文一样的操作
                for(int i=0;i<26;i++)nd[cl].e[i]=nd[q].e[i]; // 注意转移边也要操作
                nd[q].lk=nd[cur].lk=cl; // 像链表一样就把 cl 和 cur 插入进 SAM 中了
                for(;las&&nd[las].e[c]==q;las=nd[las].lk)nd[las].e[c]=cl; // 跳 link，改原有的 c 边
            }
        }
        las=cur; // 最后让代表原串的 las 变成 cur
    }
}sam;

注意到上面代码有一个枚举字符集的操作（因为转移边也要复制）。

事实上，若字符集很大，我们还能使用 map 或者 unordered_map 来存边，复制的时候直接复制即可，相当于映射一个从 char 到 int 的东西。

这样做能降低枚举字符集的复杂度。

复杂度相关证明

  1. SAM 点数至多是 2n-1：

    上文已经证明过了，在【从后缀树的角度构建】那里。

  2. SAM 边数至多是 3n-4：

    我翻遍了全网都只找到了证明边数 \sout{\le 3n-2} 的（除 OI-WIKI 太抽象看不懂之外），所以我这里就证明 3n-2 就好，事实上并不影响 SAM 的复杂度。

    • 我们知道 SAM 的转移边构成一张 DAG。
    • 考虑在这个 DAG 上弄随便一颗生成树出来（现在跟后缀树没什么关系了啊，不要往那边联想）。
    • 首先由于点数至多是 2n-1 所以树边最多是 2n-2。现在我们要证明非树边是 \le n 的。
    • 考虑搞两个集合：E=\{\texttt{非树边}\}，S=\{\texttt{原串所有后缀}\}，由于原串所有后缀是 \le n 的，我们只需要考虑证明存在一个单射函数 f:E\to S，即可证明 |E|\le n。
    • 考虑构造这个单射函数，对于每条非树边 u\to v，我们给其分配一个后缀（分成 3 段）：
      1. 从生成树根节点开始到 u 的串，由于是生成树，这样的串存在且唯一；
      2. 走非树边 u\to v；
      3. 从 v 走到任意一个终止节点（一个节点是终止节点，当且仅当任意一个原串的后缀，作为信号，在 SAM 上转移到的最终的节点）。
    • 注意第三段不一定要走树边，且我们只任取一个。
    • 我们把这三段拼起来就是原串的一个后缀，证明显然。
    • 考虑证明这个玩意是单射的：

    • 注意我们分配的东西有这个性质：u\to v 分配到的后缀，在 SAM 中转移遇到的第一条非树边就是 u\to v。

      由于只有一个“第一条非树边”，所以如果两条非树边被映射到了同一个后缀，它们一定是相同的两条非树边。

      也就是说，一个后缀只会对应一个非树边，由于一个非树边只对应一个后缀，所以它貌似是双射的（？

    • 这就证完了，好像有点不严谨？但其实无所谓啦。

  3. SAM 时间复杂度为 O(n)：

    我没证出来，真的没证出来，读者看 OI-WIKI 吧，或者自己找资料（逃。

尾言

后缀自动机这个东西真的很难理解啊，本人断断续续学了将近 2 周。如果您能看到这里，说明您非常强大。

但是我也不保证我这篇学习笔记完全正确或者讲述得完全清楚，我只是自认为讲述得挺清楚的且应该没有错误。所以如果有错误或者讲述得不清楚的地方，欢迎私信或评论指出。

在代码的海洋里，我们都是追逐数据结构星光的旅人。后缀自动机在时光里生长，每一道转移边都凝结着前人智慧的结晶。或许此刻你正为 SAM 的构建而困惑，为 link 链接的添加而辗转，但若将视角拉长，这些字符终将编织成照亮前路的银河。

对所有 OIer 而言，那些调试到凌晨的夜晚，那些反复优化的常数，那些 AC 后颤抖的指尖，都将沉淀为生命里珍贵的底色。无论未来是站在领奖台的聚光灯下，还是转身走向更广阔的天地，请记得：你曾在 OI 的星空中留下过属于自己的轨迹。

愿我们永远保持对未知的好奇，像 SAM 处理字符串般优雅地接纳所有可能的挑战。无论未来走向何方，这段为 OI 燃烧的岁月，都将是我们回望时最璀璨的星辰。前路漫漫亦灿灿，愿所有努力终不被辜负，AC 常伴，未来可期。