AC自动机解决的问题
在前缀树上玩KMP，
假设一个字符串数组中装有若干敏感词，给定一篇大文章，AC自动机就是查出大文章中包含了哪些敏感词
AC自动机是很多类似匹配算法的一个最基本的东西
步骤
先把若干敏感词建成前缀树，（前缀树，，）
敏感词之间的组织就是一颗前缀树，但是要在前缀树上面做升级
需要在每个结点上加一条fail指针（fail指针用虚线表示），头结点的fail指针指向空，并且人为规定头结点的下级直接结点的fail指针全都指向头结点，
然后底层的fail指针如何设置？
先建完前缀树，在设置fail指针，根据宽度优先的顺序设置每一个结点的fail指针，
下图中，X结点的父结点有一条走向自己的路b，但是X的父结点的fail指针指的是头结点，头结点有走向a结点、b结点、c结点的路，就是说头结点没有走向b方向的路；于是头结点顺着fail指针往下走，来到null，null结点当然也没有走向b方向的路，所以x的fail指针直接指向头结点
然后设置下图中X结点的fail指针，跟上面一样，父结点到自己方向的路是d，但是从父结点顺着fail指针找不到走向d方向的路，所以X结点的fail指针直接指向头结点
接着设置下图中X结点的fail指针（按宽度优先的顺序设置），X的父走向自己的路位c，父的fail指针指向头结点，此时头结点有走向c方向的路，所以X的fail指针就指向此时走到c方向的结点
fail指针设置规则
1）头结点的 fail 指针指向null；
2）头结点的下一级子节点的 fail 指针指向头结点；
3） 第3）种情况比较复杂；
AC自动机fail指针的实质含义
如果匹配失败，在剩下的字符串中，哪一个字符串的前缀 跟 必须包含当前字符的后缀匹配得最长，
代码
前缀树中的结点
完整代码
package com.harrison.class22;
import java.util.ArrayList;
import java.util.LinkedList;
import java.util.List;
import java.util.Queue;
/**
* @author Harrison
* @create 2022-04-02-10:21
* @motto 众里寻他千百度，蓦然回首，那人却在灯火阑珊处。
*/
public class Code03_ACAutomaton {
// 前缀树的结点
public static class Node{
// 如果一个Node，end为空，说明不是结尾
// 如果end不为空，表示这个点是某个字符串的结尾，end的值就是这个字符串
public String end;
// 只有在上面的end变量不为空的时候，endUse才有意义
// 表示，这个字符串之前没有加过答案，防止重复收集答案
public boolean endUse;
public Node fail;
// 前缀树下级的路，假设大文章，所有敏感词都是小写，就可以固定26长度
public Node[] nexts;
public Node(){
endUse=false;
end=null;
fail=null;
nexts=new Node[26];
}
}
public static class ACAutomaton{
private Node root;
// 对于AC自动机来说字符一定是放在路上的，而不是放在结点上，跟前缀树一样
public ACAutomaton(){
root=new Node();
}
// 建前缀树的过程，有多少个敏感词就调用多少次insert方法
// 前缀树建好后，再调用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){
cur.nexts[index]=new Node();
}
cur=cur.nexts[index];
}
cur.end=s;
}
// 注意：不是设置弹出结点自己的fail指针
// 而是弹出结点给它所有的子去设置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++){// 所有的路
// cur->父亲 i号儿子，必须把i号儿子的fail指针设置好
if(cur.nexts[i]!=null){// 如果真的有i号儿子
cur.nexts[i].fail=root;// 先设置成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]);
}
}
}
}
// 大文章
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) {
ACAutomaton ac = new ACAutomaton();
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);
}
}
}
