AC自动机详解（Python语言实现多模式字符串匹配算法）

AC自动机的核心组成部分

• Trie 树（前缀树）：用于存储所有待匹配的关键词。
• 失败指针（Failure Link）：当当前字符无法继续匹配时，跳转到最长公共后缀对应的节点，避免回溯。
• 输出函数：记录每个节点是否为某个关键词的结尾，并保存匹配到的关键词。

Python实现AC自动机步骤

我们将分三步实现：

1. 构建 Trie 树
2. 构建失败指针（使用 BFS）
3. 进行文本匹配

第1步：定义 Trie 节点

class TrieNode:    def __init__(self):        self.children = {}          # 子节点字典        self.fail = None            # 失败指针        self.word_end = None        # 如果是关键词结尾，存储关键词        self.output = []            # 输出列表（可存储多个关键词）

第2步：构建 AC 自动机

from collections import dequeclass ACAutomaton:    def __init__(self):        self.root = TrieNode()    def add_word(self, word):        """向Trie树中添加一个关键词"""        node = self.root        for char in word:            if char not in node.children:                node.children[char] = TrieNode()            node = node.children[char]        node.word_end = word        node.output.append(word)    def build_failures(self):        """使用BFS构建失败指针"""        queue = deque()                # 初始化：根节点的所有直接子节点的fail指向root        for child in self.root.children.values():            child.fail = self.root            queue.append(child)                # BFS遍历        while queue:            current_node = queue.popleft()                        for char, child in current_node.children.items():                # 找到当前节点的fail节点                fail_node = current_node.fail                                # 沿着fail链向上找，直到找到有char子节点的节点或回到root                while fail_node and char not in fail_node.children:                    fail_node = fail_node.fail                                # 设置child的fail指针                child.fail = fail_node.children[char] if fail_node and char in fail_node.children else self.root                                # 合并output：把fail节点的output也加入当前节点                child.output += child.fail.output                                queue.append(child)

第3步：匹配文本

    def search(self, text):        """在文本中搜索所有关键词，返回匹配结果列表"""        node = self.root        results = []                for i, char in enumerate(text):            # 如果当前节点没有char子节点，沿fail指针回退            while node and char not in node.children:                node = node.fail                        if node is None:                node = self.root            else:                node = node.children[char]                        # 检查当前节点是否有匹配的关键词            if node.output:                for word in node.output:                    start_index = i - len(word) + 1                    results.append((start_index, word))                return results

完整使用示例

# 创建AC自动机ac = ACAutomaton()# 添加关键词keywords = ["he", "she", "his", "hers"]for word in keywords:    ac.add_word(word)# 构建失败指针ac.build_failures()# 搜索文本text = "ushers"matches = ac.search(text)print("匹配结果：")for pos, word in matches:    print(f"位置 {pos}: '{word}'")# 输出：# 位置 1: 'she'# 位置 2: 'he'# 位置 3: 'hers'

应用场景

AC自动机广泛应用于：

• 敏感词过滤系统
• 生物信息学中的DNA序列匹配
• 日志分析中的关键词提取
• 搜索引擎的关键词高亮

总结

通过本教程，我们学习了 AC自动机 的基本原理和 Python实现AC自动机 的完整过程。它是一种强大的 多模式匹配 工具，特别适合需要同时查找多个关键词的场景。掌握这一算法，不仅能提升你的编程能力，还能解决实际工程中的性能瓶颈问题。

希望这篇关于 字符串匹配算法 的入门教程对你有所帮助！动手试试吧，你会发现AC自动机其实并不难。