Aho-Corasick自动机（多模式匹配算法）

问题描述
Aho-Corasick自动机是一种高效的多模式匹配算法，用于在文本中同时查找多个模式串的所有出现位置。例如，在敏感词过滤场景中，需要检测一段文本是否包含任意一个敏感词（模式串）。朴素的解法是逐个模式串进行单模式匹配（如KMP算法），但时间复杂度为O(m1 + m2 + ... + mk + n × k)，其中k为模式串数量，n为文本长度，mi为第i个模式串长度。Aho-Corasick算法通过构建有限状态自动机（Finite State Automaton）将时间复杂度优化至O(n + m1 + m2 + ... + mk + z)，其中z为匹配总数。

核心概念与步骤
算法分为三个步骤：构建Trie树、添加失败指针（类似KMP的next数组）、文本匹配。

1. 构建Trie树

• 将所有模式串插入一棵Trie树，每个节点代表一个状态（即某个前缀）。
• 根节点对应空字符串，每条边表示一个字符的转移。
• 若某个节点对应一个模式串的结束，则标记该节点为“输出节点”（可能同时匹配多个模式串，如"he"和"she"）。

示例：模式串["she", "he", "his", "hers"]  
Trie树结构（简化表示）：  
根 → 's' → 'h' → 'e' (输出: "she")  
         → 'i' → 's' (输出: "his")  
   → 'h' → 'e' (输出: "he")  
         → 'e' → 'r' → 's' (输出: "hers")

2. 构建失败指针（Failure Links）
失败指针的作用：当当前状态无法继续匹配文本的字符时，自动跳转到另一个状态，避免回溯文本指针。

• 采用BFS遍历Trie树，根节点的失败指针为null（或指向自身）。
• 对每个节点u（其通过字符c指向子节点v）：
  a. 若u为根节点，则v的失败指针指向根节点。
  b. 否则，设u的失败指针指向节点p，检查p是否存在通过字符c的转移：
  • 若存在，则v的失败指针指向p的子节点（通过c转移得到）。
  • 若不存在，则递归地检查p的失败指针，直到根节点。
• 同时，若v的失败指针指向的输出节点包含其他模式串（如"he"是"she"的后缀），则将它们合并到v的输出集合（通过输出链）。

示例：节点"she"的失败指针指向"he"（因为"he"是"she"的最长后缀且存在于Trie中）。  
节点"hers"的失败指针指向节点"ers"？不，需通过失败链递归：  
- 'h'的失败指针指向根（无前缀匹配）。  
- 'e'的失败指针通过根检查：根无'e'转移，故指向根。  
- 实际构建时，通过BFS逐层计算：  
  节点"h"的失败指针指向根；  
  节点"she"的失败指针：父节点"sh"的失败指针指向"h"（通过字符'h'转移），再从"h"检查'e'转移，存在"he"节点，故指向"he"。

3. 文本匹配流程

• 初始化当前状态为根节点，遍历文本的每个字符c。
• 若当前状态存在通过c的转移，则转移到子节点。
• 若不存在转移：
  a. 若当前状态不是根节点，通过失败指针回溯，直到找到转移或到达根节点。
  b. 若到达根节点且根节点无c转移，则保持根节点为当前状态。
• 检查当前状态及其失败链上的所有输出节点，记录匹配的模式串位置。

示例：文本"ushers"  
- 字符'u'：根节点无'u'转移，保持根状态。  
- 字符's'：根有's'转移，进入状态"s"。  
- 字符'h'：从"s"转移至"sh"。  
- 字符'e'：从"sh"转移至"she"，输出"she"；同时检查失败指针指向"he"，输出"he"。  
- 字符'r'：从"she"无'r'转移，通过失败指针跳转到"he"，再从"he"转移至"her"。  
- 字符's'：从"her"转移至"hers"，输出"hers"。  
最终匹配："she"（位置2-4）、"he"（位置3-4）、"hers"（位置2-6）。

优化与扩展

• 通过压缩失败指针（如直接指向下一个有效状态）避免递归跳转，即构建确定有限自动机（DFA）。
• 应用场景：病毒特征检测、基因序列分析、关键词过滤等需高效多模式匹配的领域。

通过以上步骤，Aho-Corasick算法将多模式匹配转化为单次文本扫描，极大提升了效率。