当前位置：首页 > news >正文

AC自动机-1

news 2025/7/18 22:27:50

AC自动机（Aho-Corasick Automaton）是一种高效的多模式字符串匹配算法。它是由Alfred Aho和Margaret Corasick在1975年提出的。这种算法可以在一次扫描输入文本的情况下,同时查找多个模式串。

基本概念

Trie树
1. AC自动机是基于字典树数据结构构建的
2. 字典树可以高效地存储和检索多个模式串
Fail指针（失败指针）
- 为了加速模式匹配的过程，AC自动机引入了fail指针的概念。
- Fail指针连接着Trie树中的各个节点，当匹配过程中发生失配时，fail指针可以帮助我们快速跳转到下一个可能匹配的位置。
- 每个节点的fail指针指向的是当前节点所表示的字符串的最长后缀匹配的节点。

构造过程

首先根据多个模式串(待查询子串)构建Trie树。
然后通过广度优先搜索（BFS）的方法为Trie树中的每个节点添加fail指针。
最后，使用构建好的AC自动机在文本中查找所有的模式串。

Trie树的构造比较简单，在此不再赘述。fail指针的构造和KMP算法中next数组的构建有些相似，但也有不同点：

共同点：两者同样是在失配的时候用于跳转的指针。
不同点：next 数组求的是最长的相同前后缀，而 fail 指针指向所有模式串的前缀中匹配当前状态的最长后缀。

fail指针的构造过程如下：

考虑字典树中当前的结点 $u$ , $u$ 的父结点是 $p$ , $p$ 通过字符 $c$ 的边指向 $u$ ，即 $\text{trans}(p,c) = u$ 。假设深度小于 $u$ 的所有结点的 fail 指针都已求得。

如果 $\text{trans}(\text{fail}[p],c)$ 存在：则让 $u$ 的 fail 指针指向 $\text{trans}(\text{fail}[p],c)$ 。相当于在 $p$ 和 $\text{fail}[p]$ 后面加一个字符 $c$ ，分别对应 $u$ 和 $\text{fail}[u]$ 。
如果 $\text{trans}(\text{fail}[p],c)$ 不存在：那么我们继续找到 $\text{trans}(\text{fail}[\text{fail}[p]],c)$ 。重复 1 的判断过程，一直跳 fail 指针直到根结点。
如果依然不存在，就让 fail 指针指向根结点。

如此即完成了 $\text{fail}[u]$ 的构建。

图解示例：

下面是字符串 i、 he、 his、 she、 hers 组成的Trie树和fail指针。

匹配过程

当文本中的字符与当前节点匹配时，就沿着子节点继续向下匹配。
如果失配，就根据fail指针回退到下一个可能的匹配位置。
这个过程会一直持续到找到所有的匹配位置或者遍历完整个文本。

代码示例


import java.util.*;public class ACAutomaton2 {private final ACNode root;public ACAutomaton2() {root = new ACNode();}// AC自动机的节点private static class ACNode {ACNode[] children = new ACNode[26]; // 假设只有小写字母ACNode fail; // 失败指针boolean isEndOfWord; // 标记是否为单词的结尾int length; // 如果是单词结尾，则记录单词长度}// 将模式串插入到Trie树中public void insert(String word) {ACNode node = root;for (char ch : word.toCharArray()) {int index = ch - 'a';if (node.children[index] == null) {node.children[index] = new ACNode();}node = node.children[index];}node.isEndOfWord = true;node.length = word.length();}// 构建失败指针public void buildFailurePointers() {Queue<ACNode> queue = new LinkedList<>();root.fail = null;queue.add(root);// 广度优先遍历while (!queue.isEmpty()) {ACNode current = queue.remove();for (int i = 0; i < 26; i++) {ACNode child = current.children[i];if (child != null) {if (current == root) {child.fail = root;} else {ACNode fail = current.fail;while (fail != null) {ACNode failChild = fail.children[i];if (failChild != null) {child.fail = failChild;break;}fail = fail.fail;}if (fail == null) {child.fail = root;}}queue.add(child);}}}}// 搜索文本中的所有模式串public List<Map.Entry<Integer, Integer>> search(String text) {List<Map.Entry<Integer, Integer>> resList = new LinkedList<>();ACNode node = root;for (int i = 0; i < text.length(); i++) {int index = text.charAt(i) - 'a';while (node != root && node.children[index] == null) {node = node.fail; // 失败指针发挥作用的地方}node = (node.children[index] != null) ? node.children[index] : root;ACNode temp = node;while (temp != root) {if (temp.isEndOfWord) {int startPos = i - temp.length + 1;int endPos = i + 1;// 与Java风格保持一致， end - start == length// System.out.println("Pattern found at index " + startPos + " to " + endPos);resList.add(new AbstractMap.SimpleEntry<>(startPos, endPos));}temp = temp.fail;}}return resList;}public static void main(String[] args) {ACAutomaton2 acAutomaton = new ACAutomaton2();acAutomaton.insert("he");acAutomaton.insert("she");acAutomaton.insert("hers");acAutomaton.insert("his");acAutomaton.buildFailurePointers();String longText = "ahishers";List<Map.Entry<Integer, Integer>> resList = acAutomaton.search(longText);System.out.println(resList);for (Map.Entry<Integer, Integer> e : resList) {System.out.println(longText.substring(e.getKey(), e.getValue()));}}
}

理解下search过程中的内部while循环，需要从当前节点开始，遍历所有可能的路径（即沿着Fail指针回溯），检查是否有匹配的关键词。例如示例中，找到 she 之后，如果不回溯，则无法正确找到 he 。