[TOC] # 1 AC自动机 KMP算法解决的问题是，在一个大字符串中，求目标match串存在还是不存在，最早存在的地方在哪 AC自动机要解决的问题是，在一个文章中，有一些候选字符串，求这个文章中命中了哪些候选串。 ## 1.1 AC自动机的实现 为每一个候选串建立一个前缀树，每个树节点都有一个fail指针。头节点fail指针人为规定指向null，第一层节点的fail指针人为规定，指向头节点。建立好前缀树后，宽度优先遍历设置全部的fail指针 > 比较绕，看不懂看代码 宽度优先遍历设置fali的指针的过程，如果某个节点的指针指向null,孩子的fail指针指向当前的父亲；如果某个节点的fail指针指向不为空的节点A,A孩子的路径为B,那么A的fali指针有没有指向B的路径，如果有，A孩子的fail指针，指向父亲节点的fail指针指向的B；如果父亲没有指向B的路，再找fail直到为null后，孩子fail指针指向头结点 ```Java package class08; import java.util.ArrayList; import java.util.LinkedList; import java.util.List; import java.util.Queue; public class Code01_AC { // 前缀树的节点 public static class Node { // 如果一个node，end为空，不是结尾 // 如果end不为空，表示这个点是某个字符串的结尾，end的值就是这个字符串 public String end; // 只有在上面的end变量不为空的时候，endUse才有意义 // 表示，这个字符串之前有没有加入过答案 public boolean endUse; public Node fail; public Node[] nexts; public Node() { endUse = false; end = null; fail = null; // 假设前缀树的节点上的值只是小写字母，有26个指向。经典前缀树 nexts = new Node[26]; } } // AC自动机 public static class ACAutomation { private Node root; // 建头结点 public ACAutomation() { root = new Node(); } // 先建前缀树，建好之后再build所有节点的fail指针 public void insert(String s) { char[] str = s.toCharArray(); Node cur = root; int index = 0; for (int i = 0; i < str.length; i++) { index = str[i] - 'a'; if (cur.nexts[index] == null) { Node next = new Node(); cur.nexts[index] = next; } cur = cur.nexts[index]; } cur.end = s; } // 建立所有节点的fail指针 public void build() { Queue<Node> queue = new LinkedList<>(); queue.add(root); Node cur = null; Node cfail = null; while (!queue.isEmpty()) { // 当前节点弹出， // 当前节点的所有后代加入到队列里去， // 当前节点给它的子去设置fail指针 // cur -> 父亲 cur = queue.poll(); for (int i = 0; i < 26; i++) { // 所有的路 if (cur.nexts[i] != null) { // 找到所有有效的路 cur.nexts[i].fail = root; // cfail = cur.fail; while (cfail != null) { if (cfail.nexts[i] != null) { cur.nexts[i].fail = cfail.nexts[i]; break; } cfail = cfail.fail; } queue.add(cur.nexts[i]); } } } } // build好之后，可以查文章有哪些候选串 public List<String> containWords(String content) { char[] str = content.toCharArray(); Node cur = root; Node follow = null; int index = 0; List<String> ans = new ArrayList<>(); for (int i = 0; i < str.length; i++) { index = str[i] - 'a'; // 路 // 如果当前字符在这条路上没配出来，就随着fail方向走向下条路径 while (cur.nexts[index] == null && cur != root) { cur = cur.fail; } // 1) 现在来到的路径，是可以继续匹配的 // 2) 现在来到的节点，就是前缀树的根节点 cur = cur.nexts[index] != null ? cur.nexts[index] : root; follow = cur; while (follow != root) { if(follow.endUse) { break; } // 不同的需求，在这一段之间修改 if (follow.end != null) { ans.add(follow.end); follow.endUse = true; } // 不同的需求，在这一段之间修改 follow = follow.fail; } } return ans; } } public static void main(String[] args) { ACAutomation ac = new ACAutomation(); ac.insert("dhe"); ac.insert("he"); ac.insert("abcdheks"); // 设置fail指针 ac.build(); List<String> contains = ac.containWords("abcdhekskdjfafhasldkflskdjhwqaeruv"); for (String word : contains) { System.out.println(word); } } } ```