24-《进阶》AC自动机和卡特兰数.md

[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指针指向头结点

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

}