AC自动机实战指南（Python语言AC自动机优化与高效多模式字符串匹配）

第一步：构建基础 Trie 树

首先，我们将所有关键词插入到一棵 Trie 树中。每个节点代表一个字符，路径表示一个单词。

class TrieNode:    def __init__(self):        self.children = {}        self.fail = None        self.output = []  # 存储以该节点结尾的关键词class ACAutomaton:    def __init__(self):        self.root = TrieNode()    def add_word(self, word):        node = self.root        for char in word:            if char not in node.children:                node.children[char] = TrieNode()            node = node.children[char]        node.output.append(word)  

第二步：构建失败指针（Failure Links）

失败指针的作用类似于 KMP 中的 next 数组。当当前字符匹配失败时，自动跳转到最长公共后缀对应的节点继续匹配。

from collections import dequedef build_failure_links(self):    queue = deque()    # 初始化：根节点的所有子节点的 fail 指向 root    for child in self.root.children.values():        child.fail = self.root        queue.append(child)    while queue:        current_node = queue.popleft()        for char, child in current_node.children.items():            # 找到当前字符在 fail 路径上的下一个匹配点            fail_node = current_node.fail            while fail_node and char not in fail_node.children:                fail_node = fail_node.fail            child.fail = fail_node.children[char] if fail_node and char in fail_node.children else self.root            # 合并 output（可选优化）            child.output += child.fail.output            queue.append(child)# 将方法绑定到类（实际使用中应放在类内）ACAutomaton.build_failure_links = build_failure_links  

第三步：执行匹配

现在我们可以用构建好的 AC 自动机在文本中快速查找所有关键词了。

def search(self, text):    node = self.root    results = []    for i, char in enumerate(text):        # 沿着 fail 链回退直到找到匹配或回到根        while node and char not in node.children:            node = node.fail        if node:            node = node.children[char]        else:            node = self.root  # 安全兜底        # 收集所有匹配结果        for word in node.output:            results.append((i - len(word) + 1, word))    return resultsACAutomaton.search = search  

第四步：Python AC自动机优化技巧

虽然上述实现已经能工作，但在处理大规模数据时仍可优化：

• 预合并 output：在构建失败指针时，将 fail 节点的 output 合并到当前节点，避免匹配时递归查找。
• 使用字典替代 defaultdict：避免不必要的内存开销。
• 缓存热点路径：对高频字符路径做局部优化（进阶）。
• 使用 Cython 或 Numba：对性能瓶颈部分进行加速（适用于超大规模场景）。

完整使用示例

# 创建 AC 自动机ac = ACAutomaton()# 添加关键词keywords = ["中国", "中华", "华为", "苹果", "apple"]for word in keywords:    ac.add_word(word)# 构建失败指针ac.build_failure_links()# 在文本中搜索text = "我爱中华，也喜欢华为和apple产品。"matches = ac.search(text)print("匹配结果：")for pos, word in matches:    print(f"位置 {pos}: '{word}'")  

总结

通过本教程，你已经掌握了 AC自动机 的基本原理、Python 实现及优化方法。无论是用于高效文本搜索算法开发，还是构建敏感词过滤系统，AC 自动机都是一个强大而优雅的工具。

记住，Python AC自动机优化的关键在于减少不必要的跳转和内存分配。在实际项目中，可根据数据规模选择是否引入更高级的优化策略。

希望这篇教程能帮助你在 多模式字符串匹配 的道路上走得更远！