学习一下ac自动机,多个模式串匹配一串文本,找到文本中模式串匹配的个数

package main

import (
	"fmt"
)

//字典树(前缀树),ac自动机基础
type Node struct { //字典树
	next [26]* Node
	fail *Node //失配指针
	flag bool
}


//构建字典树
func build(root *Node ,str string){
	pre:=root
	var ptr *Node
	order:=0 //索引
	for i:=0;i<len(str);i++{
		order = int(str[i]-'a')
		if pre.next[order]==nil{
			ptr = new(Node)
			for j:=0;j<26;j++{
				ptr.next[j] = nil
			}
			ptr.flag = false
			ptr.fail = nil
			pre.next[order] = ptr  //设置下标
		}
		pre = pre.next[order]
	}
	pre.flag = true
}


//寻找失配指针,从根开始,把子节点的失配找到
func disposeFail(root *Node){
	//层序遍历
	queue:=make([]*Node,0)
	var pre,ptr *Node
	queue = append(queue,root)
	for len(queue)!=0{
		pre=queue[0]
		queue = queue[1:]
		ptr=nil //每次都初始化
		for i:=0;i<26;i++{
			if pre.next[i]!=nil{ //子节点存在
				if pre==root{  //根则
					pre.next[i].fail = root
				}else{
					ptr = pre.fail
					for ptr!=nil{  //向上找失配对的指针
						if ptr.next[i]!=nil{
							pre.next[i].fail = ptr
							break
						}
						ptr = ptr.fail
					}
					if ptr==nil{ //回溯到root,则失配指向root
						pre.next[i].fail = root
					}
				}
				queue = append(queue,pre.next[i]) //子节点加入队列
			}
		}
	}
}


//具体匹配
func matchMultiPattern(root *Node,str string)int{
	order:=0
	count:=0
	var pre,ptr *Node
	pre = root
	for i:=0;i<len(str);i++{
		order = int(str[i]-'a')
		for pre.next[order]==nil&&pre!=root{
			pre = pre.fail
		}
		//找模式串
		pre = pre.next[order]
		if pre==nil{  //没找到开启下一轮
			pre = root
			continue
		}
		ptr = pre  //匹配该点之后沿失败回溯,判断其他点
		for ptr!=root{
			if ptr.flag==true{  //到模式串结尾,需要1决定是否增加1
				count++
				ptr.flag=false  //计算过,改为false
			}else{
				break
			}
			ptr = ptr.fail //找失配指针1
		}
	}
	return count
}




func main(){
	trim:=new(Node)
	strs:=[]string{"long","java","life","python","short"}
	for _,v:=range strs{
		build(trim,v)
	}
	//构建失配
	disposeFail(trim)
	fmt.Println(matchMultiPattern(trim,"lifeisshortsoistudypython"))
}