Aho-Corasick 算法详解：高效多模式字符串匹配

Aho-Corasick 算法（简称 AC 自动机）是一种用于多模式字符串匹配的高效算法。它由 Alfred V. Aho 和 Margaret J. Corasick 于 1975 年提出。该算法的核心优势在于能够在一个文本中同时搜索多个模式字符串，且时间复杂度与模式数量无关，仅与文本长度和匹配总数线性相关。

1. 算法核心原理

AC 算法本质上是 Trie 树（字典树） 与 KMP 算法（失败指针思想） 的结合。

1. Trie 树构建：将所有模式串构建成一棵字典树，实现前缀共享。
2. 失败指针（Failure Link）：类似于 KMP 的 next 数组，当当前字符匹配失败时，利用失败指针跳转到另一个节点继续匹配，避免回溯文本指针。
3. 输出链接（Output Link）：用于收集当前节点及其失败路径上所有匹配到的模式串。

1.1 构建流程图解

假设模式串集合为：["he", "she", "his", "hers"]

步骤 1：构建 Trie 树

(root)
 ├── 'h'
 │    ├── 'e' (匹配："he")
 │    │    └── 'r'
 │    │         └── 's' (匹配："hers")
 │    └── 'i'
 │         └── 's' (匹配："his")
 └── 's'
      └── 'h'
           └── 'e' (匹配："she")

步骤 2：构建失败指针 (Fail Pointer)

失败指针指向当前节点所代表字符串的最长真后缀所在的节点。

• root 的 fail 指向 root。
• 第一层节点（h, s）的 fail 指向 root。
• 节点 s->h (路径 "sh")：最长后缀 "h" 在 Trie 中存在，故 fail 指向 root->h。
• 节点 s->h->e (路径 "she")：最长后缀 "he" 在 Trie 中存在，故 fail 指向 root->h->e。

2. 算法详细步骤

2.1 Trie 构建

1. 创建一个根节点。
2. 遍历每个模式串，将字符依次插入 Trie。
3. 在模式串结束的节点标记该模式（通常存储在 output 列表中）。

2.2 失败函数构建 (BFS)

使用广度优先搜索（BFS）逐层计算失败指针：

1. 初始化：根节点的子节点的 fail 指针指向根节点，并入队。
2. 遍历：取出队首节点 current，遍历其子节点 child (字符为 c)。
3. 查找：沿着 current.fail 向上查找，直到找到一个节点拥有字符 c 的子节点，或者到达根节点。
4. 设置：将 child.fail 指向找到的那个子节点。
5. 继承输出：child.output 应包含 child.fail.output 中的模式（因为后缀匹配也意味着模式匹配）。

2.3 匹配过程

1. 从根节点开始，指针 node 指向当前状态。

2. 读取文本字符 char：

   • 若 node 有 char 子节点，移动到该子节点。
   • 若没有，沿 fail 指针向上跳，直到找到有 char 子节点的祖先或回到根。
3. 若到达新节点，检查该节点及其 fail 链上的 output，记录所有匹配到的模式。

3. 时间复杂度分析

注意：相比于对每个模式串单独进行 KMP 匹配（$O(n \times k)$，k 为模式串数量），AC 算法在处理大量模式串时效率提升显著。

4. 示例 walkthrough

文本: "ushers"
模式: ["he", "she", "his", "hers"]

最终输出: [(1, 'she'), (2, 'he'), (3, 'hers')] (索引从 0 开始)

5. Python 代码实现

以下实现包含了详细的注释，并优化了边界处理。

from collections import deque
from typing import List, Tuple, Dict

class TrieNode:
    def __init__(self):
        self.children: Dict[str, 'TrieNode'] = {}
        self.fail: 'TrieNode' = None
        self.output: List[str] = []  # 存储以该节点结尾的模式串

class AhoCorasick:
    def __init__(self, patterns: List[str]):
        self.root = TrieNode()
        self._build_trie(patterns)
        self._build_failure_links()

    def _build_trie(self, patterns: List[str]):
        """构建字典树"""
        for pattern in patterns:
            node = self.root
            for char in pattern:
                if char not in node.children:
                    node.children[char] = TrieNode()
                node = node.children[char]
            node.output.append(pattern)

    def _build_failure_links(self):
        """构建失败指针 (BFS)"""
        queue = deque()
        
        # 1. 初始化第一层节点的 fail 指针指向 root
        for node in self.root.children.values():
            node.fail = self.root
            queue.append(node)

        # 2. BFS 遍历
        while queue:
            current_node = queue.popleft()
            
            for char, child_node in current_node.children.items():
                # 查找失败指针目标
                fail_node = current_node.fail
                while fail_node is not None and char not in fail_node.children:
                    fail_node = fail_node.fail
                
                # 设置 fail 指针
                child_node.fail = fail_node.children[char] if fail_node else self.root
                
                # 继承输出：如果 fail 节点也是某个模式的结尾，则当前节点也间接匹配了该模式
                child_node.output += child_node.fail.output
                
                queue.append(child_node)

    def search(self, text: str) -> List[Tuple[int, str]]:
        """在文本中搜索所有模式"""
        node = self.root
        results = []
        
        for i, char in enumerate(text):
            # 匹配失败时沿 fail 指针回溯
            while node is not None and char not in node.children:
                node = node.fail
            
            # 如果回溯到 None (理论上不会发生，因为 root.fail 通常处理为 root 或 None 保护)
            if node is None:
                node = self.root
                continue
            
            # 匹配成功，向下移动
            node = node.children[char]
            
            # 收集所有匹配结果
            if node.output:
                for pattern in node.output:
                    # 计算起始索引
                    start_index = i - len(pattern) + 1
                    results.append((start_index, pattern))
                    
        return results

# --- 示例使用 ---
if __name__ == "__main__":
    patterns = ["he", "she", "his", "hers"]
    text = "ushers"
    
    ac = AhoCorasick(patterns)
    matches = ac.search(text)
    
    print(f"文本：{text}")
    print(f"模式：{patterns}")
    print(f"匹配结果 (索引，模式): {matches}")
    # 预期输出：[(1, 'she'), (2, 'he'), (3, 'hers')]

6. 应用场景

AC 自动机因其高效性，广泛应用于需要关键字过滤或多特征匹配的场景：

1. 内容安全与过滤

   • 敏感词检测（如评论系统、聊天室）。
   • 垃圾邮件识别（匹配大量垃圾关键词）。
   • 版权内容侵权检测。

2. 网络安全 (IDS/IPS)

   • 入侵检测系统（如 Snort），通过匹配网络包中的攻击特征签名。
   • 病毒特征码扫描。

3. 生物信息学

   • DNA/RNA 序列分析，同时搜索多个基因片段。

4. 搜索引擎与 IDE

   • 代码高亮（匹配大量关键字）。
   • 全文检索中的多关键词高亮。

7. 算法对比总结

提示：如果模式串包含通配符或复杂正则逻辑，AC 自动机不适用，应使用正则引擎；如果仅是纯字符串多匹配，AC 自动机性能最优。

8. 总结

Aho-Corasick 算法是解决多模式匹配问题的标准工具。它通过空间换时间（构建 Trie 和 Fail 表），将多次扫描文本转化为一次扫描，极大地提升了处理效率。理解其 Trie 结构 与 失败指针跳转逻辑 是掌握该算法的关键。