AC自动机（Aho-Corasick Algorithm）原理与实现

1. 问题描述

AC自动机（Aho-Corasick Algorithm）是一种多模式匹配算法，用于在一个主串中同时查找多个模式串。例如，在敏感词过滤系统中，给定一个文本（主串）和一个敏感词列表（多个模式串），需要快速找出所有出现在文本中的敏感词及其位置。如果使用KMP算法，需要对每个模式串单独匹配，效率较低（时间复杂度为O(m×n)，其中m是模式串数量，n是主串长度）。AC自动机通过构建一个有限状态自动机，可以在O(n)的时间复杂度内完成多模式匹配。

2. 核心思想

AC自动机结合了Trie树和KMP算法的思想：

• Trie树：用于存储所有模式串，实现共享前缀，减少空间占用。
• KMP的next数组思想：在Trie树的每个节点上增加一个fail指针（类似于KMP的next数组），用于匹配失败时的状态转移。

3. 分步详解

步骤1：构建Trie树

将所有模式串插入到一棵Trie树中。每个节点代表一个字符，从根节点到某个节点的路径表示一个模式串的前缀。

• 例如，模式串为["he", "she", "his", "hers"]，构建的Trie树如下（括号内为节点编号）：

         (0)
        /  |  \
       h   s   e
      /     |    \
    (1)e    (2)h  (3)r
    /         |      \
  (4)         (5)e    (6)s
  /              \
  

(7) (8)

节点编号：`h(1), e(4), s(8)`等。其中，节点4、5、7、8是某些模式串的终点（如节点4对应`"he"`，节点7对应`"she"`）。

---

#### **步骤2：构建fail指针**
fail指针的作用是：**当当前字符匹配失败时，跳转到另一个前缀相同的最长后缀节点**。这类似于KMP算法中的“部分匹配表”。
- **定义**：对于节点`u`，其fail指针指向节点`v`，使得从根节点到`v`的路径字符串，是从根节点到`u`的路径字符串的**最长后缀**。
- **构建方法（BFS层次遍历）**：
1. 根节点的fail指针指向`NULL`（或自己）。
2. 对于根节点的所有子节点，其fail指针指向根节点。
3. 对于其他节点`u`（假设其父节点为`p`，通过字符`c`转移到`u`）：
   - 首先找到`p`的fail指针指向的节点`q`。
   - 检查`q`是否有通过字符`c`转移的子节点`v`：
     - 如果存在，则`u`的fail指针指向`v`。
     - 如果不存在，则继续查找`q`的fail指针（即`q = q->fail`），直到根节点。
4. 如果最终没有找到，则`u`的fail指针指向根节点。

- **示例**（接上例Trie树）：
- 节点1（`h`）：父节点是根节点，fail指向根节点0。
- 节点2（`s`）：父节点是根节点，fail指向根节点0。
- 节点4（`e`，路径`"he"`）：
  - 父节点1（`h`）的fail指向0。
  - 检查节点0是否有子节点`e`？存在节点3（`e`），因此节点4的fail指向节点3。
- 节点5（`e`，路径`"she"`）：
  - 父节点2（`s`）的fail指向0。
  - 检查节点0是否有子节点`e`？存在节点3，因此节点5的fail指向节点3。
- 节点7（`e`，路径`"hers"`中的`e`）：
  - 父节点6（`r`）的fail需计算：节点6的父节点3（`e`）的fail指向0，检查节点0是否有子节点`r`？无，继续查0的fail（NULL），因此节点6的fail指向0。
  - 现在对于节点7：父节点6的fail指向0，检查节点0是否有子节点`e`？有节点3，因此节点7的fail指向节点3。

---

#### **步骤3：搜索匹配**
从主串的第一个字符开始，依次遍历每个字符，同时在Trie树上进行状态转移：
1. 初始化当前节点`p`为根节点。
2. 对于主串中的每个字符`c`：
 - 如果`p`有通过`c`转移的子节点，则`p`移动到该子节点。
 - 如果没有，则通过`fail`指针回溯（`p = p->fail`），直到找到存在`c`转移的节点，或回到根节点。
3. 在每一步中，检查当前节点`p`及其所有`fail`路径上的节点，是否为一个模式串的终点（即“输出”所有匹配的模式串）。

- **示例**：主串`"ushers"`，模式串`["he", "she", "his", "hers"]`。
- 状态转移：
  - 字符`u`：根节点无`u`子节点，`p`保持为根节点。
  - 字符`s`：根节点有`s`子节点（节点2），`p`移动到节点2。
  - 字符`h`：节点2有`h`子节点（节点5），`p`移动到节点5。
  - 字符`e`：节点5有`e`子节点（节点7），`p`移动到节点7。此时节点7是模式串`"she"`的终点，输出匹配。同时检查fail路径：节点7的fail指向节点3，节点3是模式串`"he"`的终点，输出匹配。
  - 字符`r`：节点7无`r`子节点，通过fail指针到节点3，节点3有`r`子节点（节点6），`p`移动到节点6。
  - 字符`s`：节点6有`s`子节点（节点8），`p`移动到节点8。节点8是模式串`"hers"`的终点，输出匹配。

最终输出：在位置4找到`"she"`和`"he"`，在位置6找到`"hers"`。

---

### **4. 时间复杂度分析**
- **预处理**（构建Trie和fail指针）：O(ΣL)，其中L是所有模式串的总长度。
- **匹配**：O(n + z)，其中n是主串长度，z是匹配到的模式串总数。每个字符最多在Trie树上移动一次（通过子节点或fail指针），因此是线性时间。

---

### **5. 实现细节（伪代码）**
```python
class TrieNode:
  def __init__(self):
      self.children = {}  # 子节点
      self.fail = None    # fail指针
      self.output = []    # 存储以该节点结尾的模式串索引

def build_trie(patterns):
  root = TrieNode()
  for i, pattern in enumerate(patterns):
      node = root
      for ch in pattern:
          if ch not in node.children:
              node.children[ch] = TrieNode()
          node = node.children[ch]
      node.output.append(i)  # 记录模式串索引
  return root

def build_fail_pointers(root):
  from collections import deque
  queue = deque()
  # 第一层节点fail指向根
  for ch, child in root.children.items():
      child.fail = root
      queue.append(child)
  # BFS构建
  while queue:
      node = queue.popleft()
      for ch, child in node.children.items():
          # 找到fail指针指向的节点
          f = node.fail
          while f and ch not in f.children:
              f = f.fail
          child.fail = f.children[ch] if f else root
          # 合并输出（fail路径上的所有模式串）
          child.output += child.fail.output
          queue.append(child)

def ac_search(text, root, patterns):
  result = []
  node = root
  for i, ch in enumerate(text):
      # 匹配失败时跳转fail指针
      while node and ch not in node.children:
          node = node.fail
      if not node:
          node = root
          continue
      node = node.children[ch]
      # 输出所有匹配的模式串
      for idx in node.output:
          result.append((i - len(patterns[idx]) + 1, patterns[idx]))
  return result

6. 应用场景

• 敏感词过滤
• 生物信息学中的DNA序列匹配
• 网络入侵检测（匹配攻击特征）
• 代码语法检查（匹配关键字）