第 83 课 - AC 自动机

学习目标

理解多模式串匹配问题的背景与挑战。
掌握 AC 自动机（Aho-Corasick Automaton）的核心思想：结合 Trie 树与 KMP 的失败指针。
学会构建一个完整的 AC 自动机，包括构建 Trie、计算失败指针和进行文本匹配。
能够运用 AC 自动机解决实际的多模式匹配问题。

核心概念

想象一下，你正在开发一个网络安全系统，需要扫描一段文本中是否包含“病毒”、“木马”、“黑客”等多个关键词。最朴素的方法是对每个关键词都进行一次字符串搜索，但如果有成千上万个关键词，效率会非常低下。

AC 自动机正是解决这类多模式串匹配问题的利器。它的核心思想是：将所有模式串构建成一棵 Trie 树，然后在这棵树上为每个节点预处理一个“失败指针”（Fail Pointer），这个指针的作用类似于 KMP 算法中的 next 数组，用于在匹配失败时快速跳转到下一个可能匹配的位置，而无需回溯文本串。

可以这样理解：

Trie 树：将所有模式串组织成前缀树，共享公共前缀，节省空间。
失败指针 (Fail Pointer)：对于 Trie 树上的某个节点 u，它的失败指针指向另一个节点 v，使得从根节点到 v 的路径所代表的字符串，是“从根节点到 u 的路径字符串”的最长后缀（且这个后缀本身是某个模式串的前缀）。当在节点 u 匹配失败时，我们可以沿着失败指针跳转到 v，继续尝试匹配，从而避免了从文本的下一个字符重新开始所有模式的匹配。

整个过程分为三步：

建立 Trie：将所有模式串插入 Trie 树。
构建失败指针：通过 BFS（层序遍历）动态计算每个节点的失败指针。
文本匹配：用文本串在自动机上行走，根据失败指针进行跳转，并记录匹配到的模式串。

代码示例

下面是一个使用 Python 实现的 AC 自动机，包含构建和匹配功能。

from collections import deque, defaultdict

class AhoCorasick:
    def __init__(self):
        self.goto = defaultdict(dict)  # goto 函数，转移表，键为 (状态, 字符)，值为下一状态
        self.fail = {}                 # 失败函数
        self.output = defaultdict(set) # 输出函数，记录每个状态对应的模式串结束位置
        self.state_count = 0           # 状态计数器，根状态为 0

    def add_pattern(self, pattern, pattern_id):
        """将一个模式串添加到 Trie 中"""
        state = 0
        for char in pattern:
            if char not in self.goto[state]:
                self.state_count += 1
                self.goto[state][char] = self.state_count
            state = self.goto[state][char]
        self.output[state].add(pattern_id)  # 在模式串的结尾状态标记其ID

    def build(self):
        """构建失败指针 (BFS)"""
        queue = deque()
        # 第一步：初始化第一层（根的直接子节点）的失败指针为 0
        for char, next_state in self.goto[0].items():
            self.fail[next_state] = 0
            queue.append(next_state)

        # 第二步：BFS 计算其他层次的失败指针
        while queue:
            current_state = queue.popleft()
            for char, next_state in self.goto[current_state].items():
                # 当前状态的失败状态
                fail_state = self.fail[current_state]
                # 沿着失败链寻找，直到找到一个状态，它能通过字符 char 转移，或者回到根
                while fail_state != 0 and char not in self.goto[fail_state]:
                    fail_state = self.fail[fail_state]
                # 如果失败链上的某个状态可以转移，则指向它转移后的状态；否则指向根
                self.fail[next_state] = self.goto[fail_state].get(char, 0)
                # 合并输出：如果失败指向的状态有输出，则当前状态也要继承
                self.output[next_state].update(self.output[self.fail[next_state]])
                queue.append(next_state)

    def search(self, text):
        """在文本中搜索所有模式串"""
        state = 0
        results = [] # 存储匹配结果 (位置, 模式ID)

        for i, char in enumerate(text):
            # 根据 goto 和 fail 函数进行状态转移
            while state != 0 and char not in self.goto[state]:
                state = self.fail[state]
            state = self.goto[state].get(char, 0)

            # 如果当前状态有输出，则找到匹配
            if self.output[state]:
                for pattern_id in self.output[state]:
                    # 注意：这里记录的是模式串的结束位置
                    # 要得到开始位置，需要知道模式串长度，这里简化处理，只记录结束位置和ID
                    results.append((i, pattern_id))
        return results

# 使用示例
if __name__ == "__main__":
    # 1. 创建 AC 自动机实例
    ac = AhoCorasick()

    # 2. 添加模式串
    patterns = ["he", "she", "his", "hers"]
    for idx, pattern in enumerate(patterns):
        ac.add_pattern(pattern, idx)

    # 3. 构建失败指针
    ac.build()

    # 4. 搜索文本
    text = "ahishers"
    matches = ac.search(text)

    # 输出结果
    print(f"文本: '{text}'")
    print(f"模式串: {patterns}")
    print(f"匹配结果 (结束位置, 模式索引): {matches}")
    # 我们可以将结果转换为更易读的格式
    readable_matches = []
    for pos, pid in matches:
        start_pos = pos - len(patterns[pid]) + 1
        readable_matches.append((start_pos, pos, patterns[pid]))
    print("匹配详情 (开始位置, 结束位置, 模式串):", readable_matches)

运行结果:

文本: 'ahishers'
模式串: ['he', 'she', 'his', 'hers']
匹配结果 (结束位置, 模式索引): [(2, 2), (3, 1), (5, 0), (7, 3)]
匹配详情 (开始位置, 结束位置, 模式串): [(1, 2, 'his'), (1, 3, 'she'), (4, 5, 'he'), (4, 7, 'hers')]

实践练习

练习 1（基础） 给定模式串集合：["abc", "bcd", "cde", "de"]，文本串："abcde"。请手动或编写代码使用 AC 自动机进行匹配，列出所有匹配到的模式串及其在文本中的位置（起始索引）。

练习 2（应用） 假设你正在开发一个敏感词过滤系统。敏感词列表为：["暴力", "色情", "赌博"]。编写一个函数 filter_text(text)，使用 AC 自动机将文本中的敏感词替换为 "***"。示例：filter_text("我们反对一切暴力和色情行为") -> "我们反对一切***和***行为"。

练习 3（进阶） 修改上面的 AhoCorasick 类，使其 search 方法不仅能返回匹配位置，还能返回每个模式串在文本中出现的总次数。提示：可以在 output 字典中存储 (模式ID, 出现次数) 或使用一个单独的计数器数组。

常见错误

失败指针构建错误：在 BFS 构建失败指针时，忘记更新当前状态的输出（self.output[next_state].update(...)），导致丢失由失败指针传递过来的模式串匹配。
状态转移混淆：在 search 函数的 while 循环中，条件 state != 0 and char not in self.goto[state] 必须同时满足。如果只检查 char not in self.goto[state]，当 state 为 0 且字符不在根节点的转移中时，会导致无限循环或错误。
输出位置理解：search 函数返回的是模式串在文本中的结束索引。要计算开始索引，必须知道模式串的长度 (len(pattern))。
根节点特殊性：根节点（状态 0）的失败指针通常定义为自身或一个特殊标记（在我们的实现中，当无法转移时默认回到 0）。确保在构建和匹配时正确处理从根节点出发的转移。

小结

AC 自动机是解决多模式串匹配问题的高效算法，其时间复杂度为 O(N + M + Z)，其中 N 是文本长度，M 是所有模式串总长度，Z 是匹配次数。
它的核心是将模式串构建成 Trie 树，并在此基础上预处理失败指针。失败指针使得匹配失败时可以“智能”地跳转，避免了不必要的回溯。
构建过程遵循三步：建立 Trie -> BFS 计算失败指针 -> 文本匹配。
理解失败指针的含义（最长的、是某个模式串前缀的后缀）是掌握 AC 自动机的关键，它本质上是 KMP 算法在多模式场景下的推广。
AC 自动机广泛应用于敏感词过滤、病毒特征码检测、生物信息学中的序列匹配等领域。

练习编辑器

rust