宽度优先遍历设置fali的指针的过程，如果某个节点的指针指向null,孩子的fail指针指向当前的父亲；如果某个节点的fail指针指向不为空的节点A,A孩子的路径为B,那么A的fali指针有没有指向B的路径，如果有，A孩子的fail指针，指向父亲节点的fail指针指向的B；如果父亲没有指向B的路，再找fail直到为null后，孩子fail指针指向头结点

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;

public void build() {

Queue<Node> queue = new LinkedList<>();

queue.add(root);

Node cur = null;

Node cfail = null;

// 当前节点弹出，

// 当前节点的所有后代加入到队列里去，

// 当前节点给它的子去设置fail指针

// cur -> 父亲

cur = queue.poll();

for (int i = 0; i < 26; i++) { // 所有的路

if (cur.nexts[i] != null) { // 找到所有有效的路

cfail = cur.fail;

while (cfail != null) {

if (cfail.nexts[i] != null) {

cur.nexts[i].fail = cfail.nexts[i];

}

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