AC自动机算法详解及模板

AC 自动机（Aho-Corasick 自动机）是一种用于多模式字符串匹配的高效算法。它结合了 Trie 树和 KMP 算法的思想，能够在 O(n + m + z) 的时间复杂度内完成字符串匹配，其中 n 是文本长度，m 是所有模式串的总长度，z 是匹配结果的数量。

1. AC 自动机的基本思想

AC 自动机主要由以下几个部分组成：

Trie 树：用于存储所有的模式串。
失败指针：用于处理不匹配的情况，类似于 KMP 算法中的部分匹配表。
输出函数：用于记录匹配的模式串。

2. AC 自动机的构建步骤

2.1 插入模式串

首先，我们构建一个 Trie 树，将所有要匹配的模式串插入到树中。

输入模式串： "he", "she", "his", "hers"

Trie 树结构：

        root
        /  \
       h    s
      /      \
     e        h
             / \
            i   e
           /
          s

2.2 构建失败指针

接下来，我们为 Trie 树中的每个节点建立失败指针。如果当前节点无法匹配下一个字符，则通过失败指针回溯到更高层次的节点。

构建失败指针的步骤：

使用 BFS 遍历 Trie 树，初始化根节点的失败指针为自身。
对于每个节点，遍历其子节点，设置失败指针。

失败指针示例：

        root
        /  \
       h    s
      /|    |
     e |    h
        |   / \
        |  i   e
        | /
        s

节点 h 的失败指针指向 root。
节点 s 的失败指针指向 root。
节点 e 的失败指针指向 root。
节点 i 的失败指针指向 h（因为 h 是 i 的最长前缀）。
节点 hers 的失败指针指向 hers 本身。

2.3 匹配过程

在匹配过程中，从根节点开始，逐字符遍历文本字符串。如果当前字符在当前节点的子节点中，则继续向下遍历；如果不在，则通过失败指针回溯，直到找到匹配或到达根节点。

3. 示例代码

以下是 AC 自动机的基本实现模板：

class ACNode:
    def __init__(self):
        self.children = {}
        self.fail = None
        self.output = []

class ACAutomaton:
    def __init__(self):
        self.root = ACNode()

    def insert(self, pattern):
        node = self.root
        for char in pattern:
            if char not in node.children:
                node.children[char] = ACNode()
            node = node.children[char]
        node.output.append(pattern)

    def build_fail_pointers(self):
        from collections import deque
        queue = deque([self.root])
        while queue:
            current = queue.popleft()
            for char, child in current.children.items():
                # Find fail pointer
                fail_node = current.fail
                while fail_node and char not in fail_node.children:
                    fail_node = fail_node.fail
                child.fail = fail_node.children[char] if fail_node else self.root
                # Merge output
                if child.fail:
                    child.output.extend(child.fail.output)
                queue.append(child)

    def search(self, text):
        node = self.root
        results = []
        for char in text:
            while node and char not in node.children:
                node = node.fail
            if node:
                node = node.children[char]
            else:
                node = self.root
            
            if node.output:
                results.extend(node.output)
        return results

# 使用示例
ac = ACAutomaton()
patterns = ["he", "she", "his", "hers"]
for pattern in patterns:
    ac.insert(pattern)
ac.build_fail_pointers()
text = "ushers"
matches = ac.search(text)
print(matches)  # 输出匹配的模式串