小刻也能看懂的后缀自动机详解

智子 · 2022-11-10 22:01:45 · 个人记录

前置知识

自动机

OI 中提到的自动机（AC 自动机、后缀自动机等）一般指“确定有限状态自动机（DFA）”。

形式化地说，一个 确定有限状态自动机（DFA） 由以下五部分构成：

字符集（\Sigma），该自动机只能输入这些字符。
状态集合（Q）。如果把一个 DFA 看成一张有向图，那么 DFA 中的状态就相当于图上的顶点。
起始状态（start），start\in Q，是一个特殊的状态。起始状态一般用 s 表示，为了避免混淆，本文中使用 start。
接受状态集合（F），F\subseteq Q，是一组特殊的状态。
转移函数（\delta），\delta 是一个接受两个参数返回一个值的函数，其中第一个参数和返回值都是一个状态，第二个参数是字符集中的一个字符。如果把一个 DFA 看成一张有向图，那么 DFA 中的转移函数就相当于顶点间的边，而每条边上都有一个字符。

感性地理解一下，自动机相当于一张有向图，当自动机接受一个信号序列时，按照信号序列的内容在有向图上进行转移，最后通过判断是否能够被识别以及最后到达的状态来对该信号序列进行判断。

当我们使用自动机来处理字符串时，从起始状态开始按照每一位字符进行转移，如果完成所有转移后当前状态为可接受状态，这个字符串就是可接受的。

Trie 树

以 Trie 树为例，Trie 树是一个接受且仅接受给定的字符串集合中的字符串的自动机（不一定是最小的）。事实上，Trie 树是符合上述要求的所有自动机中最大的。

KMP

KMP 自动机接受且仅接受以给定的字符串为后缀的字符串。字符串在 KMP 算法中匹配的过程实际上就是在 KMP 自动机上跑的过程。

KMP 自动机的主体是一条链，每个节点向前连一条后缀链接 next 边。每次进行转移时，如果当前节点的下一个节点对应的字符就是当前转移的字符，就直接转移到下一个节点；否则递归转移到其后缀链接节点会转移到的节点。形式化的表述为：

\delta(i, c)= \begin{cases} i+1&s[i+1]=c\\ 0&s[1]\ne c\land i=0\\ \delta(\pi(i),c)&s[i+1]\ne c\land i>0 \end{cases}

AC 自动机

AC 自动机接受且仅接受以给定的字符串集合中的字符串为后缀的字符串，是 KMP 与 Trie 树的结合。在 AC 自动机中，字符串集合中的每个元素都有各自的接受状态。

定义

后缀自动机是接受一个字符串的所有后缀的最小 DFA（确定有限状态自动机）。

结构

后缀自动机（SAM）由有向无环单词图（DAWG）和后缀链接（有时也被称为 parent\ tree）组成，两部分共用相同的节点。

endpos 集合

对于字符串 S 的一个字串 s，endpos(s) 是字串 s 在 S 中出现的所有结束位置的集合。

例子：在字符串 abcdabca 中，endpos(abc) = \{3, 7\}。

endpos 等价类

在字符串 S 中，不同的字串的 endpos 集合可能是相同的，以上面的字符串为例， endpos(abc) = endpos(bc) = \{3, 7\}。

1. 对于同一个 $endpos$ 等价类中的两个非空字串 $s$ 和 $t$（$|s| > |t|$），则 $t$ 是 $s$ 的后缀，并且每次出现时都是以 $s$ 的后缀的形式出现的。 2. 对于两个非空字串 $s$ 和 $t$（$|s| > |t|$），则要么 $\operatorname{endpos}(s)\cap \operatorname{endpos}(t)=\varnothing$，要么 $\operatorname{endpos}(s)\subseteq \operatorname{endpos}(t)

在一个 endpos 等价类中，字串的长度必定填满了一段连续的 [minlen, maxlen] 区间。

性质 1 显然成立，性质 2 实际上就是性质 1 的逆命题，性质 3 也不难由性质 1 得到。

SAM 中的每一个节点都对应不同的 endpos 等价类。

因为如果两个节点的 endpos 等价类相同，进行转移时在后面添加一个字符后得到的 endpos 等价类也一定是相同的，即转移函数完全相同。

endpos 等价类的个数

endpos 等价类的个数是 O(n) 的（最多为 2n - 1），这一性质和 DAWG 的转移边一同保证了 SAM 的线性复杂度。

考虑对于一个 endpos 等价类，在其中最长的字串 s 前面添加一个字符，得到另一个子串 t。t 不在原本的 endpos 等价类中，但 t 所在的 endpos 等价类一定是原 endpos 等价类的子集。在 s 前面添加不同的字符，会得到不同的 endpos 等价类，这些 endpos 等价类彼此之间不会重叠，但都是原 endpos 等价类的子集。这相当于一个“分割” 的过程，将空串对应的 endpos 集合 \{1, 2, 3, ..., n\} 分割成若干的子集，子集再往下分割，最后每个集合的大小都为 1。

后缀链接

对于一个 endpos 集合 u，其中最长的字符串为 s，s 的一部分较长的连续后缀同样也在 u 中，剩余较短的后缀则不在 u 里面。我们记其中最长的后缀为 t ，t 所在的 endpos 集合为 v，则我们称 u 的后缀链接为 v，link(u) = v。按照这一定义，有 minlen(u) = maxlen(link(u)) + 1。

将每个点与其后缀链接连边，最终会得到一棵树，有时也被称为 parent\ tree。这棵树的根节点是空串对应的 endpos 等价类 \{1, 2, 3, ..., n\}。

考虑上一节中提到的 endpos 等价类的性质，我们也可以对于每个 endpos 等价类按照包含关系，在每个集合与它在前面添加字符“分裂”得到的子节点之间连边，这也会得到一棵树，并且与后缀链接得到的树相同。

SAM 的转移函数（DAWG）

节点 u 在经过转移边 c 后转移到了节点 v，代表 endpos 等价类 u 中的所有字符在末尾添加一个字符 c 之后得到的字符串全部都在 endpos 等价类 v 中。一个 endpos 等价类可能会由几个不同的 endpos 等价类转移而来。所以这些节点之间由转移函数构成了一个有向无环图。

这个有向无环图也被称为有向无环单词图（Directed Acyclic Word Graph）。

构造

后缀自动机的构造是在线的，换句话说，我们每次往后缀自动机中添加一个字符 c，并得到新串对应的后缀自动机。

我们首先新建一个节点 cur，表示当前字符串 s + c，last 为之前的字符串 s 所对应的节点。设 p 初始为 last。记 len(u) 为节点 u 中的最长子串的长度。

len(cur) = len(last) + 1

通过跳 link(p) 遍历 s 的后缀链接，直到 p 有到 c 的转移或者 p 为空状态为止。如果一直没有到 c 的转移，说明字符 c 在原串 s 没有出现过。这时可以将 link(cur) 置为 1 （起始状态）。
如果找到了 \delta(p, c) = q，意味着存在 s 的一个最长的后缀 t（t 在节点 p 中），t+c 在 s 中出现过（t+c 在节点 q 中）。
如果 t+c 在 q 中是最长的子串，即 len(q) = len(p) + 1，那么直接将 link(cur) 置为 q 就能满足后缀自动机的性质。
如果 t+c 在 q 中不是最长的子串，即 len(q) > len(p) + 1，意味着 q 中包含比 t+c 更长的子串。并且，因为 t+c 是 s 最长的以 c 结尾的后缀，所以 q 中的其它字串并不是新串 s+c 的后缀。换句话说，在新串的后缀自动机里， q 中这部分子串的 endpos 集合比 q 中长度小于等于 len(p) + 1 的子串少一个 n+1。
所以，此时我们必须将 q 分裂成两个节点，一个包含 q 中长度小于等于 len(p) + 1 的子串，另一个包含 q 中长度大于 len(p) + 1 的子串。
新建一个节点 clone，len(clone) = len(p) + 1。由 clone 的定义可知 link(clone) 就是原来的 link(q)，而link(q) 则应该被置为 clone。（相当于在链表中插入一个元素。）clone 的转移边显然与 q 完全相同（因为字串本身并没有改变，只是分成了两类）。
最后我们还需要将 p 及其部分后缀（parent\ tree 上的部分祖先）到 c 的转移从 q 改为 clone。（因为这部分转移到的字符串已经由 q 转移到 clone 中了。）

代码实现如下：

namespace SAM {
    int ch[MAXN * 2][26], len[MAXN * 2], link[MAXN * 2];
    int tot = 1, last = 1;

    void extend(int c) {
        int cur = ++tot, p = last;
        len[cur] = len[p] + 1;
        while(p && !ch[p][c]) {
            ch[p][c] = cur;
            p = link[p];
        }
        if(!p) {
            link[cur] = 1;
        } else if(len[p] + 1 == len[ch[p][c]]) {
            link[cur] = ch[p][c];
        } else {
            int q = ch[p][c], clone = ++tot;
            memcpy(ch[clone], ch[q], sizeof(ch[q]));
            len[clone] = len[p] + 1;
            link[clone] = link[q];
            while(p && ch[p][c] == q) {
                ch[p][c] = clone;
                p = link[p];
            }
            link[cur] = link[q] = clone;
        }
        last = cur;
    }
}

应用

SAM 在应用中还有其它非常有用的性质。

判断子串

SAM 接受的字符串是给定字符串的所有后缀，所以如果将中间的节点也看作接受状态，SAM 接受的字符串就是给定字符串的所有后缀的前缀，即给定字符串的子串。

所以，当我们需要判断一个字符串是否是给定字符串的子串时，我们只需要将其在 SAM 上匹配，如果一直可以转移就是原串的子串。

不同子串个数

原字符串的每个子串都一定属于某个 endpos 等价类中，而每个 endpos 等价类 u 的大小就等于 len(u) - len(link(u))（endpos 等价类的性质）。所以原串的不同子串个数就等于：

\sum_{u} len(u) - len(link(u))

这个问题也可以从 DAWG 的角度来考虑，因为原字符串的所有子串都对应 DAWG 中一条从起始状态开始的路径。设 dp_u 为从节点 u 出发的路径数，则

dp_{u}=1+\sum_{\delta(u, c) = v}dp_{v}

答案为 dp_1 - 1。（不考虑空串。）

例题：

洛谷 P2408 不同子串个数

SDOI2016 生成魔咒

字符集

部分题目中的字符集较大，无法用数组储存，这时我们需要在每个节点上维护一个 STL map 用于转移。例如 SDOI2016 生成魔咒。

字典序第 k 大子串

原字符串中的字典序第 k 大子串就是 DAWG 中的字典序第 k 大路径。通过上一小节中的 DP 我们可以得到从每个点出发的路径个数，在 DAWG 中 dfs 就能找到答案。

例题：

TJOI2015 弦论

SUBLEX

最小表示法

将字符串 s 复制为 ss 并建立 SAM，在 SAM 上找字典序最小的长度为 |s| 的子串即可。

例题：

洛谷 P1368 【模板】最小表示法

子串出现次数

考虑 endpos 集合的“分裂”性质，在 parent\ tree 上 dfs 计算每个 endpos 集合的大小即可。这里需要注意的是，对于原字符串的前缀，它们所在的 endpos 集合 u 可能只包含它自身，此时将 siz(u) 置为 1；也可能包含多个位置，此时这个前缀位置会在分裂时丢失（因为前缀前面没有字符），也要先将 siz(u) 置为 1，dfs 时再累加子树和。

子串第一次出现的位置

对于每个节点 u，我们额外维护一个属性 firstpos(u)。

新建节点 cur 时，firstpos(cur) = len(p) + 1

复制节点 clone 时，firstpos(clone) = firstpos(q)

子串出现的所有位置

使用线段树合并，实现过程类似于求子串出现个数，在每个前缀对应的节点赋值当前位置，然后从子节点往上合并。

需要注意的是，这里的线段树合并在合并完后仍然会访问被合并的节点，所以在合并线段树 p 和 q 时不能直接合并到 p 上，需要新建一个节点 now。空间大小也需要开普通线段树合并的两倍。

事故案例

从上往下遍历后缀链接树

可以直接用 DFS 实现，但常数较大。注意到对于一个节点 u，一定有 len(u) > len(link(u)) ，所以我们可以将节点按照 len 排序。因为值域很小，可以使用基数排序，复杂度为 O(n)。

for(int i = 1; i <= SAM::tot; i++) cnt[SAM::len[i]]++;
for(int i = 1; i <= SAM::tot; i++) cnt[i] += cnt[i - 1];
for(int i = 1; i <= SAM::tot; i++) a[cnt[SAM::len[i]]--] = i;

子串对应的 endpos 等价类

对于给定 s 的子串 s_{l...r}，我们先记录 s 的所有前缀 s_{1...i} 对应的节点，再从 s_{1...r} 开始倍增向上跳后缀链接 link。预处理复杂度 O(n\log n)，单词询问复杂度 O(\log n)。

给定字符串是否在给定子串中出现

为了判断字符串 t 是否是 s_{l...r} 的子串，我们先定位到字符串 t 在 SAM 上的对应节点，然后再查询该节点的 endpos 是否有在 [l + |t| - 1, r] 之间的元素即可。

例题：

TJOI / HEOI2016 字符串

最长公共子串

过程类似 KMP，将一个字符串在另一个字符串的 SAM 上匹配，如果能转移则直接转移，否则遍历后缀链接，直到能转移或者遇到起始状态。同时维护当前匹配的最长长度 l。

代码实现如下：

int ans = 0, l = 0, p = 1;
    for(int i = 0; i < m; i++) {
        int c = t[i] - 'a';
        if(SAM::ch[p][c]) {
            l++;
            p = SAM::ch[p][c];
        } else {
            while(p && !SAM::ch[p][c]) p = SAM::link[p];
            if(p != 0) {
                l = SAM::len[p] + 1;
                p = SAM::ch[p][c];
            } else {
                l = 0; p = 1;
            }
        }
        ans = max(ans, l);
    }

在匹配时删除前端字符

直接将当前匹配长度减一，如果匹配长度小于等于当前节点 u 的 len(link(u)) 则转移到后缀链接 u = link(u)。

例题：

CF235C Cyclical Quest

参考资料

后缀自动机(SAM) - OI Wiki

后缀自动机学习笔记 - Menci's OI Blog

后缀自动机（SAM）学习笔记 - ouuan的博客

史上最通俗的后缀自动机详解- KesdiaelKen 的博客