AC 自动机

What · 是什么

AC（Aho–Corasick）自动机以 Trie 结构为基础、结合 KMP 失配指针思想，解决『一次匹配多个模式串』问题。构建分两步：① 把所有模式串插入 Trie；② BFS 构建 fail 指针——fail[u] 指向 u 的最长真后缀状态（即字典树中存在的最长后缀字符串所对应的节点）。常配合『Trie 图』优化：把不存在的转移补全为 fail 的转移，使匹配过程每字符 O(1) 无需回溯。匹配：文本串沿 Trie 图走，每到一个节点沿 fail 链累加所有匹配模式。优化：fail 树拓扑/DFS 求和可在 O(len) 统计每个模式出现次数。时间复杂度：建 O(Σ|s_i|+n·字符集)，匹配 O(|S|+z)（z 为匹配总数）。

Why · 为什么

How · 实现

伪代码

# 节点: tr[u][26] 转移(Trie图), fail[u], cnt[u]
def build():
  q = deque(根的所有直接儿子)   # 根儿子 fail=0
  while q:
    u = q.popleft()
    for c in range(26):
      v = tr[u][c]
      if v:
        fail[v] = tr[fail[u]][c]
        q.append(v)
      else:
        tr[u][c] = tr[fail[u]][c]   # 补全 Trie图
def query(text):
  u = 0; res = 0
  for ch in text:
    u = tr[u][ch]
    v = u
    while v and cnt[v]: res += cnt[v]; cnt[v]=0; v = fail[v]
  return res
# 求每个模式次数: 命中节点 acc++ -> 按 fail 树逆拓扑累加

Python 实现

from collections import deque


class AhoCorasick:
    """AC 自动机: Trie + 失配指针(fail) + Trie图(补全转移).
    build 后 tr[u][c] 为补全后的转移; fail[u] 指向最长后缀状态.
    匹配复杂度 O(文本长) 不计输出, 建图 O(模式串总长 * 字符集)."""
    def __init__(self, alpha_size=26):
        self.alpha = alpha_size
        self.tr = [[0] * self.alpha]    # tr[0] 全 0 表示根
        self.fail = [0]
        self.cnt = [0]                  # 该节点作为模式串结尾的次数(0/1)
        self.used = []                  # 匹配时已计入答案的模式(去重)

    def add(self, s):
        u = 0
        for ch in s:
            c = ord(ch) - ord('a')
            if self.tr[u][c] == 0:
                self.tr[u][c] = len(self.tr)
                self.tr.append([0] * self.alpha)
                self.fail.append(0)
                self.cnt.append(0)
                self.used.append(False)
            u = self.tr[u][c]
        self.cnt[u] += 1

    def build(self):
        """BFS 构建 fail, 同时把不存在的转移补全为 fail 的转移(Trie图)."""
        q = deque()
        for c in range(self.alpha):
            v = self.tr[0][c]
            if v:
                self.fail[v] = 0
                q.append(v)
        while q:
            u = q.popleft()
            for c in range(self.alpha):
                v = self.tr[u][c]
                if v:
                    self.fail[v] = self.tr[self.fail[u]][c]
                    q.append(v)
                else:
                    self.tr[u][c] = self.tr[self.fail[u]][c]

    def query(self, text):
        """返回文本中出现的模式串个数(每个模式串计一次)."""
        u = 0
        res = 0
        for ch in text:
            c = ord(ch) - ord('a')
            u = self.tr[u][c]
            v = u
            while v and self.cnt[v]:
                res += self.cnt[v]
                self.cnt[v] = 0
                v = self.fail[v]
        return res

    def query_count_all(self, text):
        """返回每个模式串在文本中的出现次数(含重叠), 借助 fail 树自底向上累加.
        要求已 build. 返回数组 acc, 下标为节点号, acc[结束节点] 即该模式串出现次数."""
        n = len(self.tr)
        acc = [0] * n
        u = 0
        for ch in text:
            c = ord(ch) - ord('a')
            u = self.tr[u][c]
            acc[u] += 1
        # BFS 序(按真实 Trie 边, 深度非降). 逆序累加 => 自底向上沿 fail 树求和
        for v in reversed(self._order):
            acc[self.fail[v]] += acc[v]
        return acc

    def _record_order(self):
        """在 build 前调用: 用真实 Trie 边做 BFS, 记录节点序."""
        order = [0]
        q = deque([0])
        while q:
            u = q.popleft()
            for c in range(self.alpha):
                v = self.tr[u][c]
                if v:
                    order.append(v)
                    q.append(v)
        self._order = order

def build_ac(patterns):
    """便捷封装: 返回 (ac, end_nodes). end_nodes[i] 为第 i 个模式串的结束节点."""
    ac = AhoCorasick()
    ends = []
    for p in patterns:
        ac.add(p)
    # 记录真实儿子(在补全前)
    ac._record_order()
    for p in patterns:
        u = 0
        for ch in p:
            u = ac.tr[u][ord(ch) - ord('a')]
        ends.append(u)
    ac.build()
    return ac, ends


if __name__ == "__main__":
    patterns = ["she", "he", "his", "hers"]
    text = "ushersheishis"
    ac, ends = build_ac(patterns)
    assert ac.query("ushersheishis") >= 1
    # 计数每种模式
    ac2, ends2 = build_ac(patterns)
    acc = ac2.query_count_all(text)
    # 暴力验证
    def brute(patterns, text):
        res = {}
        for p in patterns:
            c = 0
            for i in range(len(text) - len(p) + 1):
                if text[i:i+len(p)] == p:
                    c += 1
            res[p] = c
        return res
    expected = brute(patterns, text)
    for p, e in zip(patterns, ends2):
        assert acc[e] == expected[p], (p, acc[e], expected[p])
    print("ac-automaton: all tests passed")

易错点

• 根的儿子 fail 忘了置 0（应直接入队而非根本身）
• build 时没做 Trie 图补全，匹配时回溯 fail 太慢
• 朴素 query 每次跳 fail 链在重叠数据上 TLE（必须拓扑/DFS 优化）
• 多模式计数时重复清零 cnt 导致多模式计数丢失
• 字符集下标/文本字符越界
• 递归建树过深（总长 1e6）导致 RecursionError

例题

信源

• OI Wiki✓ https://oi-wiki.org/string/ac-automaton/
• CP-Algorithms✓ https://cp-algorithms.com/string/aho_corasick.html
• 论文✓ https://dl.acm.org/doi/10.1145/360825.360855