AC 自动机

真的比 KMP 简单！（指好理解）

前置知识

trie 树（必会）
KMP（知道一点思想就行，不用详细学习）

用途

我们知道 KMP 能够 \(\operatorname{O}(|T|+|S|)\) 匹配单个文本串 \(T\) 与模式串 \(S\)。但是如果有 \(n \leq 10^5\) 个模式串（小串）匹配一个文本串（大串）呢？AC 自动机能够在 \(\operatorname{O}(|T|+\sum |S|)\) 的复杂度内求出每一个模式串的出现次数。

核心思想和 KMP 相似，除去多余的匹配，即在当前匹配状态的基础上转移着匹配。（我也不知道我说了啥）

基本结构

多个模式串，先去重前缀，建立前缀树（即 trie 树）。 假设我们当前有四个模式串：\(\texttt{abc,ac,bc,bd}\)

对每个模式串终止字符记录其出现的次数作为其在 trie 树上对应节点的权值，然后遍历文本串的每一个字符，在 trie 树上向下走，\(ans\) 加上当前点的权值，如果走不了了就把文本串的当前指针回跳到上一个有多个子节点的节点，从 trie 树根节点继续匹配。（当然这个不重要，理解不理解无所谓）（理解不了就自己匹配一下试试）

合并了一些模式串的前缀，于是有了一定优化，但是优化还不够，考虑对后缀优化。

fail 边

含义

AC 自动机的核心就是 fail 边。

fail 边的含义：如果 \(u\) 点的 fail 边指向 \(v\)，则 \(v\) 点所代表的字符串¹是 \(u\) 点所代表的字符串的后缀，且前者是除后者自身以外满足要求的最长字符串。

先不管怎样建 fail 边，按照要求人脑建立一下，如下图：

然后假设有文本串 \(\texttt{abc}\)，进行匹配。

为什么上一次匹配的时候，我们需要把文本串的指针回跳？因为没有办法除去后缀的影响——一个模式串是另一个模式串的后缀，或前者的一部分是后者的后缀。意味着：后者匹配失败不代表前者也会匹配失败。于是我们可以记录一下合法后缀，如果匹配失败就跳到自己最长后缀所在节点上（没有的话就跳根节点），容易发现这样一直跳下去，能把最开始的串的合法后缀全部跳完！说明后缀的影响已经排除掉了。

为了方便，我们把没有合法后缀的节点的 fail 边指向根节点。

实际上此时的 fail 边的含义：无法向下一个子节点匹配（没有子节点或匹配失败）时要走的边。

动画演示：

建立

BFS 的过程。

1. 第一层（根节点为第零层）的 fail 全部指向根节点²，压入队列。

2. 取出队头，遍历子节点，如果子节点存在，假设这个子节点代表字符 \(c\)，当前节点 fail 指针指向 \(lf\)，\(lf\) 的子节点集合为 \(son\)，则将其 fail 指针指向 \(son_c\)。

没了。

优化

我们一般把 trie 树的一个节点的儿子用长度为 26 的数组存下，导致遍历子节点的时候会遍历到傻逼空节点。

对于当前节点的空子节点指针，可以直接指向当前 fail 指针指向的节点的子节点集合中，对应的子节点。

参考代码：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17

void build() {
    std::queue<i32> q;
    for (i32 i = 0; i < 26; ++i)
        if (trie[0].son[i]) q.push(trie[0].son[i]);
    while (!q.empty()) {
        i32 nod = q.front(), lfail = trie[q.front()].fail; // 当前节点和当前节点的 fail 节点
        q.pop();
        for (i32 i = 0; i < 26; ++i) {
            i32& to = trie[nod].son[i];
            if (to) {
                trie[to].fail = trie[lfail].son[i];
                q.push(to);
            } else
                to = trie[lfail].son[i]; // 节点为空
        }
    }
}