AC自动机学习笔记

ccr's notebook / 2023-08-25 / 原文

AC_Automaton=Trie+KMP!

废话

KMP

Trie

AC自动机

AC自动机就是在Trie上建立失配指针，以完成多模式串匹配的数据结构。

建立AC自动机

建立一个AC自动机通常需要两个步骤：

基础的TRIE结构：将所有的模式串构成一棵Trie。
KMP的思想：对Trie树上所有的结点构造失配指针。

然后就可以利用它进行多模式串匹配了。

insert

同Trie（一模一样）。

void insert(string s){
    int p=0;//此点编号 
   	for(int i=0;i<s.size();i++){
      	int x=num(s[i]);//编码 
		if(!nex[p][x])nex[p][x]=++cnt;//没有点就新建 
		p=nex[p][x];//更新所在点 
		b[p]++;//前缀增加 
	}
}

build

运用广搜的思想构建失配指针。

void build(){
queue<int>q;
	memset(fail,0,sizeof(fail));
	for(int i=0;i<26;i++)if(tr[0][i])q.push(nex[0][i]);
	while(!q.empty()){
    	int k=q.front();q.pop();
    	for(int i=0;i<26;i++){
        	if(nex[k][i]){
            	fail[tr[k][i]]=nex[fail[k]][i];
            	q.push(nex[k][i]);
        	}
        	else tr[k][i]=tr[fail[k]][i];
   		}
	}
}

query

失配指针都建了，查找就很简单了：

int query(string t){
	int p=0,res=0;
	for(int i=0;t[i];i++){
    	p=nex[p][t[i]-'a'];
    	for(int j=p;j&&b[j]==-1;j=fail[j])res+=b[j],b[j]=-1;
	}
	return res;
}