AC自动机详解

巨巨博客连接

Wiki-AC自动机
B站视频详解
不知道B站视频会不会变换地址，搜”UESTCACM 每周算法讲堂 AC自动机”就有了
因为学过形式语言与自动机，把书上的每个店看成一个状态，每个fail指针看成一个转移函数就可以了

代码实现

#include<bits/stdc++.h>
using namespace std;
#define ll long long 
#define MAX_N 1000006
#define MAX_Tot 500005
struct Aho{
	struct state{
		int next[26];
		int fail,cnt;
	}st[MAX_Tot];
	int size;
	queue<int>q;
	void init(){
		while(!q.empty())q.pop();
		for(int i=0;i<MAX_Tot;i++){
			memset(st[i].next,0,sizeof(st[i].next));
			st[i].fail=st[i].cnt=0;
		}
		size=1;
	}
	void insert(char *S){
		int n=strlen(S);
		int now=0;
		for(int i=0;i<n;i++){
			int c=S[i]-'a';
			if(!st[now].next[c])st[now].next[c]=size++;
			now=st[now].next[c];
		}
		st[now].cnt++;
	}
	void build(){
		st[0].fail=-1;
		//根节点的fail指针已经找到，进入队伍中 
		q.push(0);
		while(!q.empty()){
			int u=q.front();q.pop();
			//遍历与根节点的边，其实再想能不能优化这里 
			for(int i=0;i<26;i++){
				//如果存在这条边 
				if(st[u].next[i]){
					if(u==0)st[st[u].next[i]].fail=0;//这里就是位于与根节点连接的状态，他们的fail指针都指向0 
					else{
						int v= st[u].fail;//令当前节点遍历的为父亲节点，不停的往上找他的祖先 
						while(v!=-1){
							if(st[v].next[i])//如果存在一条与u-i-对应的v-i-边，则找到了 
							{
								st[st[u].next[i]].fail=st[v].next[i];
								break;//保证找的是最长的，也就是离u最近的节点 
							}
							v=st[v].fail;
						}
						if(v==-1)st[st[u].next[i]].fail=0;//如果最后没找到，那么就直接等于根节点 
					}
					q.push(st[u].next[i]);//统计完fail之后，直接就入队等待遍历 
				}
			}
		}
	}
	int Get(int u){
		int res=0;
		while(u&&st[u].cnt!=-1){
			res=res+st[u].cnt;
			st[u].cnt=-1;
			u=st[u].fail;
		}
		return res;
	}
	int match(char *S){
		int n=strlen(S);
		int res=0,now=0;
		for(int i=0;i<n;i++){
			int c = S[i]-'a';
			if(st[now].next[c]){
				now = st[now].next[c];
			}
			else{
				int p = st[now].fail;
				while(p!=-1&&st[p].next[c]==0){
					p=st[p].fail;
				}
				if(p==-1)now=0;
				else now = st[p].next[c];
			}
			if(st[now].cnt){
				res=res+Get(now);
			}
		}
		return res;
	}
}aho;
char S[MAX_N];
int main(){
	int t;
	scanf("%d",&t);
	while(t--){
		aho.init();
		int m;
		scanf("%d",&m);
		while(m--){
			scanf("%s",S);
			aho.insert(S);
		}
		scanf("%s",S);
		aho.build();
		printf("%d\n",aho.match(S));
	}
}