AC自动机-1

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

基本概念

1. Trie树

   1. AC自动机是基于字典树数据结构构建的
   2. 字典树可以高效地存储和检索多个模式串

2. Fail指针（失败指针）

   • 为了加速模式匹配的过程，AC自动机引入了fail指针的概念。
   • Fail指针连接着Trie树中的各个节点，当匹配过程中发生失配时，fail指针可以帮助我们快速跳转到下一个可能匹配的位置。
   • 每个节点的fail指针指向的是当前节点所表示的字符串的最长后缀匹配的节点。

构造过程

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

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

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

fail指针的构造过程如下：

        考虑字典树中当前的结点  ,  的父结点是  ,  通过字符  的边指向 ，即 。假设深度小于  的所有结点的 fail 指针都已求得。

1. 如果  存在：则让  的 fail 指针指向 。相当于在 和  后面加一个字符 ，分别对应  和 。
2. 如果  不存在：那么我们继续找到 。重复 1 的判断过程，一直跳 fail 指针直到根结点。
3. 如果依然不存在，就让 fail 指针指向根结点。

如此即完成了 的构建。

图解示例：

下面是字符串 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 。

思考

• 多模式让你想到哪些应用场景？比如中文分词？
• 在构建和查询时，fail指针存在多次跳转的问题，这种情况可不可以被优化呢？
• AC自动机如何结合DoubleArrayTrie呢？

参考文档

https://zh.wikipedia.org/zh-hans/AC%E8%87%AA%E5%8A%A8%E6%9C%BA%E7%AE%97%E6%B3%95
AC 自动机 - OI Wiki