BadProxyGo用AC自动机进行多模式匹配，实现流量实时分流的功能

和Trie匹配的区别就在于，Trie失配时会回到root重新匹配，AC失配时会用奇妙的方法找到与当前匹配字符拥有最大后缀的状态继续匹配，也就是把KMP算法放到了Trie上

所以重点就在于构建每个匹配状态下的失配指针，用于指示下一步

记S2 = goto(S1, C)为字典树中S1状态接收C goto S2，S2 = failure(S1)为S1的failure失配(状态)节点为S2

1. Success 接收一个匹配字符
2. Output 达到某个模式串的末尾，在Trie树中标记的output状态
3. Failure 跳转到最大后缀 记此时状态为S1状态机的上一success状态为(唯一)S2, S1与S2的goto条件为C，S2的failure状态为S3(唯一且已经存在)，测试S3的goto状态，如果存在S4 = goto(S3, C)则S4为C1的failure 即如有: S1 = success(S2, C) S3 = failure(S2) S4 = success(S3, C) 则S4 = failure(S1) failure节点从上逐层计算，所以当我们求failure(S1)时，其上一个状态S2必然已经计算过failure了 当前状态(S1)的failure状态(S4=failure(S1))的意义是在自动机中找到与S1拥有最长相同后缀的状态，而其前一个状态(S2)的failure状态(S3)和S2拥有最长相同后缀(已经确定的)，所以最长相同后缀可以再延长(通过S1=goto(S2,C), S4=goto(S3, C)的C)，那相当于S1和S4分别继承了他们唯一前一状态的最长相同后缀 当然S4直接存在是理想情况，如果S4=goto(S3, C)走不通转移不了，那就再找S3的failure, 即找到S5=failure(S3), 寻找S6=goto(S5, C)

这个东西匹配速度是只与字符串长度相关的O(n)，不受pattern数量影响, 缺点就是构建非常慢，可能需要预构建然后序列化再读取，目前的方案是拉了一个域名/IP地址库，定期预构建，把自动机数据和应用分开处理，还不错~

实现如下：very nice

 

package structure

func NewTrie() *ACAutomaton {
	trie := &ACAutomaton{
		success: make(map[uint8]*ACAutomaton),
		failure: nil,
		emit:    false,
	}
	trie.failure = trie
	return trie
}

// ACAutomaton /*
type ACAutomaton struct {
	success map[uint8]*ACAutomaton
	failure *ACAutomaton
	emit    bool
}

func (root *ACAutomaton) Add(value string) {
	curr := root
	for i := range value {
		ch := value[i]
		_, exist := curr.success[ch]
		if exist == false {
			curr.success[ch] = NewTrie()
		}
		curr = curr.success[ch]
	}
	curr.emit = true
}

func NewACAutomaton(patterns []string) *ACAutomaton {
	ac := NewTrie()
	for _, pattern := range patterns {
		ac.Add(pattern)
	}
	ac.build()
	return ac
}

func (root *ACAutomaton) MatchAny(key string) bool {
	curr := root
	for i := range key {
		success, exist := curr.success[key[i]]
		for exist == false && curr != root {
			curr = curr.failure
			success, exist = curr.success[key[i]]
		}
		if exist == true {
			curr = success
		} // else: curr == root, curr = root
		if curr.emit == true {
			return true
		}
	}
	return false
}

func (root *ACAutomaton) build() {
	queue := NewQueue[*ACAutomaton](0, 1000)
	if err := queue.Push(root); err != nil {
		panic(err)
	}
	for queue.Size() != 0 { // bfs without layer
		s2 := queue.Pop()
		for c, s1 := range s2.success {
			if err := queue.Push(s1); err != nil {
				panic(err)
			}
			s3 := s2.failure
			for {
				if s3 == root {
					s1.failure = root
					break
				}
				s4, exist := s3.success[c]
				if exist == true {
					s1.failure = s4
					break
				}
				s3 = s3.failure
			}
		}
	}
}