字符串算法之AC 自动机（Aho-Corasick Algorithm, 多模式匹配）详细解读

AC自动机（Aho-Corasick Algorithm）是一种高效的多模式字符串匹配算法，用于同时查找多个模式串（子串）在文本串中的出现位置。它结合了字典树（Trie）和有限状态机（Finite State Machine）的思想，能够在 O(n+m+z)的时间复杂度内完成匹配，其中 n 是文本的长度，m 是所有模式串的总长度，z 是匹配结果的数量。

AC自动机的基本原理

AC自动机主要通过以下几个步骤实现：

1. 构建字典树（Trie）：

   • 将所有的模式串插入到一个字典树中。字典树的每个节点代表一个字符的状态，路径上的字符代表一个模式串。

2. 构建失败指针：

   • 对字典树进行扩展，建立每个节点的失败指针。这些失败指针用于在匹配过程中提供回溯的能力，当当前字符不匹配时，利用失败指针转移到其他状态。

3. 进行模式匹配：

   • 在输入文本上进行扫描，根据字典树和失败指针进行状态转移，并记录匹配结果。

详细步骤

1. 构建字典树

• 将所有模式串插入到字典树中，构建出一个Trie树。每个节点存储该字符和指向子节点的指针。

2. 构建失败指针

• 通过BFS（广度优先搜索）遍历字典树，为每个节点计算失败指针。失败指针指向当前节点失配时应转移到的节点。

• 失败指针的构建规则：

  • 如果当前节点的某个字符与文本串不匹配，则沿着失败指针找到最长的可匹配前缀节点。

3. 进行模式匹配

• 从文本的第一个字符开始，遍历文本。
• 根据当前字符的状态，进行状态转移。若匹配成功，继续查找下一个字符；若匹配失败，则沿着失败指针进行转移。
• 若到达某个节点时标记为模式串的结束，记录该模式串的出现位置。

AC自动机的Java实现

以下是AC自动机的Java实现示例：

import java.util.ArrayList;
import java.util.HashMap;
import java.util.List;
import java.util.Map;class AhoCorasick {private class TrieNode {Map<Character, TrieNode> children = new HashMap<>();TrieNode fail; // 失败指针List<String> outputs = new ArrayList<>(); // 输出的模式串public TrieNode() {this.fail = null;}}private TrieNode root;public AhoCorasick() {root = new TrieNode();}// 插入模式串public void insert(String pattern) {TrieNode currentNode = root;for (char c : pattern.toCharArray()) {currentNode = currentNode.children.computeIfAbsent(c, k -> new TrieNode());}currentNode.outputs.add(pattern); // 将模式串存储到输出列表}// 构建失败指针public void buildFailPointers() {List<TrieNode> queue = new ArrayList<>();root.fail = root;for (TrieNode child : root.children.values()) {child.fail = root; // 根节点的失败指针指向自己queue.add(child);}while (!queue.isEmpty()) {TrieNode currentNode = queue.remove(0);for (Map.Entry<Character, TrieNode> entry : currentNode.children.entrySet()) {char c = entry.getKey();TrieNode child = entry.getValue();queue.add(child);// 查找当前节点的失败指针TrieNode failNode = currentNode.fail;while (failNode != root && !failNode.children.containsKey(c)) {failNode = failNode.fail;}child.fail = failNode.children.getOrDefault(c, root); // 失败指针child.outputs.addAll(child.fail.outputs); // 继承失败指针的输出}}}// 进行模式匹配public List<int[]> search(String text) {List<int[]> results = new ArrayList<>();TrieNode currentNode = root;for (int i = 0; i < text.length(); i++) {char c = text.charAt(i);while (currentNode != root && !currentNode.children.containsKey(c)) {currentNode = currentNode.fail; // 没有匹配，使用失败指针}currentNode = currentNode.children.getOrDefault(c, root); // 继续匹配// 如果有输出，说明找到了模式串for (String pattern : currentNode.outputs) {results.add(new int[] { i - pattern.length() + 1, pattern.length() });}}return results;}public static void main(String[] args) {AhoCorasick ac = new AhoCorasick();String[] patterns = {"he", "she", "his", "hers"};for (String pattern : patterns) {ac.insert(pattern);}ac.buildFailPointers();String text = "ushers";List<int[]> matches = ac.search(text);for (int[] match : matches) {System.out.println("Pattern found at index: " + match[0] + ", length: " + match[1]);}}
}

代码解读

1. TrieNode类：

   • TrieNode表示字典树的节点，包含子节点的映射、失败指针和输出模式串列表。

2. 插入模式串：

   • insert方法接受一个模式串，并将其插入到字典树中。每次插入都更新当前节点，并将模式串存储到输出列表中。

3. 构建失败指针：

   • buildFailPointers方法通过BFS构建失败指针，确保每个节点都有合适的失败指针，并将输出模式串从失败节点继承到当前节点。

4. 进行模式匹配：

   • search方法扫描输入文本并根据字典树和失败指针进行状态转移，记录匹配的模式串及其位置。

5. 主函数：

   • 在主函数中，创建AC自动机实例，插入多个模式串，构建失败指针，然后在文本中查找匹配并打印结果。

AC自动机的优缺点

优点

• 高效性：AC自动机在处理多个模式串时非常高效，适合需要同时查找多个模式串的场景。
• 线性时间复杂度：匹配过程的时间复杂度为 O(n+m+z)，其中 z 是匹配结果的数量。

缺点

• 空间复杂度：由于需要存储字典树和失败指针，空间复杂度相对较高，尤其是模式串数量较多时。
• 实现复杂性：相比于其他字符串匹配算法（如KMP），AC自动机的实现相对复杂，涉及到字典树的构建和失败指针的维护。

应用场景

AC自动机广泛应用于文本处理、网络监控、数据包过滤、信息检索等领域。它能够高效地处理大规模文本数据，快速匹配多个模式串，尤其适合处理多关键词搜索和匹配的场景。