什么是 AC 自动机？

AC 自动机（Aho-Corasick Automaton）是一种高效的、基于字典树（Trie）和 KMP 思想的字符串匹配算法。它能够在一个主文本串中，同时查找多个模式串的存在，且时间复杂度为线性 O(N+M)，其中 N 是主文本串长度，M 是所有模式串的总长度。

核心思想

AC 自动机巧妙地结合了两种数据结构的优点：

1. Trie (字典树): 用来存储所有的模式串。Trie 的结构使得所有模式串共享公共前缀，节省了空间。
2. 失败指针 (Fail Pointer): 这是 AC 自动机的精髓，类似于 KMP 算法中的 next 数组。每个 Trie 节点都有一个失败指针。节点 u 的失败指针指向的节点 v，代表了从根到 v 的路径所形成的字符串，是“从根到 u 的路径所形成的字符串”的 最长真后缀，并且这个后缀本身也是一个模式串的前缀。