浅谈 ACAM

Wyh_dailyAC · 2026-01-22 20:05:28 · 算法·理论

版权声明

本文遵循 CC BY-NC-ND 4.0 协议，作者：Wyh_dailyAC，转载请获得作者授权。

本文首次编写时间：2026-01-22 20:05，本文最后一次更改时间：2026-01-30 15:43。

前言

博客链接。

本文是笔者《“浅谈算法”文章集》的第一个讲解类文章。

本文无图，主要讲 ACAM 的思想，故本文适合对 AC 自动机的结构有大致了解，但不了解其具体思想的人。

在本文中，如无特殊标注，字符串的下标从 1 开始。

upd (2026/1/30)：修复了一处笔误；增加了博客链接。

AC 自动机的来历

引用百度百科上的一句话：

AC 自动机（外文名：Aho-Corasick automaton）是 1975 年由贝尔实验室提出的多模式匹配算法，基于字典树（Trie）结构结合 KMP 算法失败指针思想构建。

这里有几个关键词：Trie，KMP 失败指针思想。

下面主要介绍“KMP 失败指针思想”相关内容，对 Trie 的讲解有所缺失。不太了解 Trie 的可以看：OI Wiki - Trie。

AC 自动机的前置知识

KMP 的前缀函数 & 失配指针思想

先定义前缀函数为一个长 n 的数组 \pi[i]，简单来说，\pi[i] 就是子串 s[1\dots i] 最长的相等的真前缀与真后缀的长度。

下面直接讲解最优化的前缀函数求法，这里就运用了失配指针思想。

设若已经处理出了 \pi[1\dots i-1]，考虑如何求 \pi[i]。

注意到 \pi[i-1] 到 \pi[i] 的增量最大为 1，最小为 -\pi[i-1]，这里我们先考虑增加 1 的情况。

不妨举个例子：\texttt{abcab}。

可以看出，\texttt{abcab} 的 \pi[1\dots4] 分别为 0,0,0,1，如果想要让 \pi[5]=\pi[4]+1，那么必须有 s[1+1]=s[4+1] 才行（这里把下标写作 1+1,4+1，是为了体现出该点是原 \pi[4] 的边界点的延伸）。这个条件显然是充要的，且在 s 中确实成立，所以这是一个正确的判定策略，即当 s[\pi[i-1]+1]=s[i-1+1] 时，有 \pi[i]=\pi[i-1]+1。

接下来讨论 s[\pi[i-1]+1]\ne s[i-1+1] 的情况，这就叫失配，即失去（进一步的）匹配。

失去进一步的匹配，就要尝试更劣的情况，“退而求其次”。

具体是怎么样“退而求其次”呢？

考虑我们是怎么在 \pi[i-1]\rightarrow \pi[i] 这个过程中失配的，显然是因为在尝试进一步的匹配时，对 \pi[i-1] 所对应的最长 border 进行了加入 s[i] 的操作，导致新 border 不满足其自身性质，那我们如果要退而求其次，就应该尝试去寻找 s[1\dots i-1] 中次长的 border，并判断其加入 s[i] 后是否满足 border 性质，如此往复，直到新加入后确实满足 border 性质——我们总是想贪心地令 \pi[i] 最大，这显然要一个一个、从长到短的去试，又因为新加入字符所能带来的增量最大也就 1，而不会出现小 border 在增量后超越大 border 的情况，所以这个贪心思想是正确的。

现在，问题转化为了串 s[1\dots i-1] 在当前 border 上失配时，该如何寻找次长 border——这就是失配指针思想：在失去匹配时退而求其次，考虑次优情况（这个思想在 AC 自动机上会有更深刻的体现）。

先下一个结论：对于 s[1\dots i] 的最长 border，其次长 border 的长度为 \pi[\pi[i]]，即 s[1\dots \pi[i]] 的最长 border 长度。下证此结论。

证明：

先证明 \pi[\pi[i]] 作为 s[1\dots i] 的 border 长度的合法性。由定义知 s[1\dots\pi[i]]=s[i-\pi[i]+1\dots i],s[i-\pi[i]+1\dots i-\pi[i]+\pi[\pi[i]]=s[i-\pi[\pi[i]]+1\dots i]，可得 s[1\dots\pi[\pi[i]]]=s[i-\pi[i]+1\dots i-\pi[i]+\pi[\pi[i]]，等量代换即可得 s[1\dots\pi[\pi[i]]]=s[i-\pi[\pi[i]]+1\dots i]，所以“\pi[\pi[i]] 可以作为 s[1\dots i] 的 border 的长度”。

设若 s[1\dots i] 的次长 border 的长度不为 \pi[\pi[i]]，而是比 \pi[\pi[i]] 更优的 tlen（注意 \pi[\pi[i]]<tlen<\pi[i]）。根据 border 定义，有 s[1\dots tlen]=s[i-tlen+1\dots i]，又因为 s[1\dots\pi[i]]=s[i-\pi[i]+1\dots i] 且 \pi[\pi[i]]<tlen<\pi[i]，所以有 s[1\dots tlen]=s[i-\pi[i]+1\dots i-\pi[i]+1+tlen-1]，即 s[1\dots tlen]=s[i-\pi[i]+1\dots i-\pi[i]+tlen]，等量代换得到 s[i-\pi[i]+1\dots i-\pi[i]+tlen]=s[i-tlen+1\dots i]，则 s[i-\pi[i]+1\dots i] 即 s[1\dots \pi[i]] 的最长 border 的长度 \pi[\pi[i]]\ge tlen，这显然与 \pi[\pi[i]]<tlen 的假设条件矛盾，故假设不成立。假设不成立，则证得 s[1\dots i] 的次长 border 的长度绝对不会比 \pi[\pi[i]] 更优，结合前面“\pi[\pi[i]] 可以作为 s[1\dots i] 的 border 的长度”的结论，综上证得“对于 s[1\dots i] 的最长 border，其次长 border 的长度为 \pi[\pi[i]]”。原结论证毕。

将上面结论推广，我们就有了求当前 border 的次长 border 长度的算法，于是有下面的“求 \pi[i]”代码。

for (int i = 2; i <= lent + 1 + lens; ++i) {
    int j = pi[i - 1];
    while (j > 0 && cur[i] != cur[j + 1]) j = pi[j];
    if (cur[i] == cur[j + 1]) pi[i] = j + 1;
}

上面代码求的是一个长为 lens+lent+1 的字符串的 \pi 数组。

KMP 其实就是构造“模式串 + 特殊字符 + 文本串”的新串，然后求 \pi 数组的算法，其思想就是求 \pi 时“退而求其次”的失配指针思想。

AC 自动机相关的定义

定义 ch 数组表示 Trie 的出边数组，定义一个 Trie 上节点的 fail 指针指向 Trie 上代表其最长真后缀的节点（如 Trie 上无该点真后缀，则指向源点）（注意 fail 指针的构建由浅到深）。

为什么 ACAM 要在 Trie 上建立

这其实挺显然的吧，因为 Trie 可以表示字符串的所有子串，因为 Trie 很省节点，因为 Trie 可以根据节点所在层和入边字符来保证节点的性质独立性，因为 Trie 有很多优良的性质与适用场景……

上面所例举的，无不是 ACAM 在 Trie 上建立的理由。

AC 自动机的建立

归根结底，ACAM 就是 KMP 的一个多模版的拓展，所以其所有的内容都是可以类比 KMP 的内容的，要坚信、理解这一点，才能通过 KMP 的思想，来完全理解 ACAM 的思想。

理解 fail 指针的算法意义

这一部分非常重要，读者要与 KMP 的思想结合着思考，才能更深刻地理解 fail 指针的意义。

考虑下面一个问题（AC 自动机模板）：

给你一个文本串 S 和 n 个模式串 T_{1 \sim n}，请你分别求出每个模式串 T_i 在 S 中出现的次数。

我们先不管 fail 的构造，也不考虑暴力跳 fail 链 / 其他算法的时间复杂度，我们就考虑最朴素的方法怎么做。

考虑最朴素的方法，就是枚举每一个子串，然后查这个子串是否为一个模式串。

这个方法怎么放到 fail 树上实现呢？

显然，子串其实就是对一个串的前缀再扣掉一部分的前缀，也就是一个前缀串的后缀。

前缀串就是 Trie 上节点啊！而 fail 指针指向的是一个 Trie 上节点的真后缀啊！那跳 fail 就是枚举前缀的后缀（即子串）啊！

于是我们有了一个最朴素的方法：先把模式串插入 Trie，且标记结束节点，然后把文本串放到 Trie 上查询，对于查询到的节点暴力地跳 fail 链（枚举其子串），并查询当前节点的标记情况（如有标记则答案增加，否则不变）。

但这就显着这个 fail 树建立带来的优化没多少啊，况且 fail 优化的意义与 KMP 的思想呢？

很显然，我们要尝试将模式串结束节点的标记同步到其他的 fail 树节点上（注意 Trie 树和 fail 树的节点其实是共用的，以下可能会混用）。

我们可以采用树上差分那种链上前缀和思想，把标记产生的贡献打到 fail 树的节点上。

接下来我们要决定转移标记的顺序——注意到，fail 树由深向浅指向，所以其绝对是一个 DAG。

DAG？很明显可以拓扑排序——这样就保证了标记同步的顺序。

好了，设若我们已经完成了拓扑优化，那显然我们还要把暴力跳 fail 的时间复杂度优化掉。