AC自动机详解（Python实现多模式字符串匹配的高效算法教程）

AC自动机的核心组成部分

• 字典树（Trie）：用于存储所有关键词。
• 失败指针（Failure Link）：当匹配失败时，跳转到另一个可能匹配的位置，避免回溯。
• 输出函数（Output）：记录当前节点是否是一个关键词的结尾，以及是哪些关键词的结尾。

Python实现AC自动机步骤详解

第1步：构建字典树

首先，我们定义一个 TrieNode 类来表示字典树的节点：

class TrieNode:    def __init__(self):        self.children = {}      # 子节点字典        self.fail = None        # 失败指针        self.word_end = []      # 以该节点结尾的关键词列表

第2步：插入关键词

接下来，我们构建一个 AhoCorasick 类，并实现插入关键词的方法：

class AhoCorasick:    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.word_end.append(word)  # 标记该节点为某个关键词的结尾

第3步：构建失败指针（BFS）

使用广度优先搜索（BFS）来设置每个节点的失败指针：

from collections import dequedef build_fail_pointer(self):    queue = deque()    # 初始化根节点的子节点    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_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                        # 合并输出：如果失败指针指向的节点有输出，也加入当前节点            if child.fail.word_end:                child.word_end.extend(child.fail.word_end)                        queue.append(child)

第4步：搜索文本

最后，我们实现搜索方法，在文本中查找所有关键词：

def search(self, text):    results = []    current_node = self.root    for i, char in enumerate(text):        # 沿着失败指针回退，直到找到匹配或回到根节点        while current_node and char not in current_node.children:            current_node = current_node.fail                if current_node is None:            current_node = self.root        else:            current_node = current_node.children[char]                # 如果当前节点有输出，记录匹配结果        if current_node.word_end:            for word in current_node.word_end:                start_index = i - len(word) + 1                results.append((start_index, word))        return results

完整示例与测试

将上述代码整合后，我们可以这样使用 AC 自动机：

# 创建AC自动机实例ac = AhoCorasick()# 添加关键词keywords = ["he", "she", "his", "hers"]for word in keywords:    ac.add_word(word)# 构建失败指针ac.build_fail_pointer()# 搜索文本text = "ushers"matches = ac.search(text)print(matches)  # 输出: [(1, 'she'), (2, 'he'), (3, 'hers')]

总结

通过本教程，你已经掌握了如何用 Python实现AC自动机 来进行高效的多模式字符串匹配。AC自动机在实际应用中非常广泛，比如敏感词过滤、日志分析、DNA序列比对等。希望这篇AC自动机教程能帮助你深入理解这一强大算法！

如果你觉得这篇文章对你有帮助，欢迎分享给更多正在学习AC自动机的朋友！