Skip to main content

字符串算法：AC 自动机

Aiden L.7/22/24About 3 min算法算法字符串AC自动机自动机

什么是 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 的路径所形成的字符串”的 最长真后缀，并且这个后缀本身也是一个模式串的前缀。

当在主文本串中匹配时，如果当前字符无法在 Trie 树上继续前进（即 Trie[current_node][char] 不存在），我们就顺���当前节点的失败指针往回跳，直到找到一个可以匹配当前字符的节点，或者跳回根节点。这个过程保证了匹配不会中断，并且能发现所有可能存在的模式串。

算法构建流程

  1. 构建 Trie: 将所有模式串插入到一个 Trie 树中。在每个模式串的结尾节点，标记这是一个模式串的结束。
  2. 构建失败指针:
    • 使用广度优先搜索 (BFS) 来按层构建失败指针。
    • 根节点的失败指针指向自己（或 null）。
    • 对于队列中取出的节点 u，遍历其所有子节点 v（对应字符 c）：
      • 找到 u 的失败指针指向的节点 p_fail = u->fail。
      • 在 p_fail 节点上，尝试沿着字符 c 前进。如果 Trie[p_fail][c] 存在，那么 v 的失败指针就指向 Trie[p_fail][c]。
      • 如果 Trie[p_fail][c] 不存在，就继续跳 p_fail = p_fail->fail，重复此过程，直到找到或者跳回根节点。
      • 将 v 加入队列。

匹配流程

  1. 从 Trie 的根节点开始，遍历主文本串的每一个字符 c。
  2. 在当前节点 p，沿着字符 c 在 Trie 树上移动。如果 Trie[p][c] 不存在，则令 p = p->fail 并重复，直到找到或回到根。
  3. 移动到新节点 p_new 后��从 p_new 开始，沿着失败指针链一直跳回根节点。路径上遇到的所有被标记为“模式串结尾”的节点，都代表一个成功的匹配。

AC 自动机是多模式串匹配问题的最优解法之一，在文本过滤、生物信息学等领域有广泛应用。