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

[TOC]

# 1 AC自动机

KMP算法解决的问题是，在一个大字符串中，求目标match串存在还是不存在，最早存在的地方在哪

AC自动机要解决的问题是，在一个文章中，有一些候选字符串，求这个文章中命中了哪些候选串。

## 1.1 AC自动机的实现

为每一个候选串建立一个前缀树，每个树节点都有一个fail指针。头节点fail指针人为规定指向null，第一层节点的fail指针人为规定，指向头节点。建立好前缀树后，宽度优先遍历设置全部的fail指针

> 比较绕，可以考虑看代码详细步骤来理解

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



```Go
package main

import "fmt"

// Node 前缀树的节点
type Node struct {
	// 如果一个node，end为空，不是结尾
	// 如果end不为空，表示这个点是某个字符串的结尾，end的值就是这个字符串
	End string
	// 只有在上面的end变量不为空的时候，endUse才有意义
	// 表示，这个字符串之前有没有加入过答案
	EndUse bool
	Fail   *Node
	// 假设前缀树的节点上的值只是小写字母，有26个指向。经典前缀树
	Nexts []*Node
}

func InitACAutomationNode() *Node {
	root := &Node{
		End:    "",
		EndUse: false,
		Fail:   new(Node),
		Nexts:  make([]*Node, 26),
	}
	return root
}

// insert 先建前缀树，建好之后再build所有节点的fail指针
func (root *Node) insert(s string) {
	str := []byte(s)
	cur := root
	index := 0
	for i := 0; i < len(str); i++ {
		index = int(str[i] - 'a')
		if cur.Nexts[index] == nil {
			next := InitACAutomationNode()
			cur.Nexts[index] = next
		}
		cur = cur.Nexts[index]
	}
	cur.End = s
}

// 建立所有节点的fail指针
func (root *Node) build() {
	queue := make([]*Node, 0)
	queue = append(queue, root)
	var cur *Node
	var cfail *Node

	for len(queue) != 0 {
		// 当前节点弹出，
		// 当前节点的所有后代加入到队列里去，
		// 当前节点给它的子去设置fail指针
		// cur -> 父亲
		cur = queue[0]
		queue = queue[1:]

		for i := 0; i < 26; i++ { // 所有的路
			if cur != nil && cur.Nexts != nil && cur.Nexts[i] != nil { // 找到所有有效的路
				cur.Nexts[i].Fail = root
				cfail = cur.Fail

				for cfail != nil {
					if cfail.Nexts != nil && cfail.Nexts[i] != nil {
						cur.Nexts[i].Fail = cfail.Nexts[i]
						break
					}
					cfail = cfail.Fail
				}
				queue = append(queue, cur.Nexts[i])
			}
		}
	}
}


// build好之后，可以查文章有哪些候选串
func (root *Node) containWords(content string) []string {
	str := []byte(content)

	cur := root
	var follow *Node
	ans := make([]string, 0)

	for i := 0; i < len(str); i++ {
		index := int(str[i] - 'a') // 路
		// 如果当前字符在这条路上没配出来，就随着fail方向走向下条路径
		for cur.Nexts[index] == nil && cur != root {
			cur = cur.Fail
		}

		// 1) 现在来到的路径，是可以继续匹配的
		// 2) 现在来到的节点，就是前缀树的根节点
		if cur.Nexts[index] != nil {
			cur = cur.Nexts[index]
		} else {
			cur = root
		}
		follow = cur

		for follow != root {
			if follow.EndUse {
				break
			}

			// 不同的需求，在这一段之间修改
			if len(follow.End) != 0 {
				ans = append(ans, follow.End)
				follow.EndUse = true
			}
			// 不同的需求，在这一段之间修改
			follow = follow.Fail
		}
	}
	return ans
}

//he
//abcdheks
func main() {
	ac := InitACAutomationNode()
	ac.insert("ahe")
	ac.insert("he")
	ac.insert("abcdheks")
	// 设置fail指针
	ac.build()

	contains := ac.containWords("abcdhekskdjfafhasldkflskdjhwqaeruv")
	for _, word := range contains {
		fmt.Println(word)
	}
}
```