AC自动机

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);
        }
    }
}