前言

在学习AC自动机前，请确保已经学习并能熟练运用：

• KMP匹配

• 字典树

引入

在漫长的OI路途，我们难免要接触到一种叫字符串的东西。

在解决关于字符串的问题时，我们又难免要解决两个字符串匹配的问题，

比如，在一个字符串s中，字符串t出现了多少次 这些问题。（详见KMP匹配）

而在OI路途也不是一直可以一帆风顺的，万恶的出题人绝对不会总让你只匹配一个字符串，他们肯定要想方设法提高些难度，比如一个文本串匹配多个匹配串……

显然，这时候我们不可能对着那么多个字符串一个一个的做KMP，这时候就要用到本文的内容：AC自动机。

AC自动机

AC自动机是建立在字典树和KMP思想上的产物，从某种意义上来说，KMP匹配也是AC自动机的一种特殊情况（字典树只有一条链的时候）。

它通过建立所有匹配串的字典树，在每个节点建立失配指针fail来将各节点联系起来。

指针fail指向的是当前串最长后缀的节点，这样可以保证沿着fail一直跳下去，不会漏掉任何一个后缀节点。

在文本串匹配时，对于文本串的每一个前缀串，通过跳fail指针将其后缀串全部搜一遍，累加答案即可。

P3808 【模板】AC 自动机（简单版）

code：

#include<bits/stdc++.h>
using namespace std;

const int maxn=1e6+5,maxs=1e6+5;

int n,f[maxs][27],root=0,cnt=0;
int add[maxs],fail[maxs];
string s;

void insert(string s) {
	int now=root;
	for(int i=0;i<s.size();i++) {
		int c=s[i]-'a';
		if(!f[now][c]) f[now][c]=++cnt;
		now=f[now][c];
	}
	add[now]++;
	return ;
}

void build() {
	queue<int>q;
	for(int i=0;i<26;i++)
		if(f[root][i]) q.push(f[root][i]);
	while(!q.empty()) {
		int now=q.front();
		q.pop();
		for(int i=0;i<26;i++)
			if(f[now][i]) {
				fail[f[now][i]]=f[fail[now]][i];
				q.push(f[now][i]);
			}
			else f[now][i]=f[fail[now]][i];
	}
	return ;
}

int query(string s) {
	int now=root,re=0;
	for(int i=0;i<s.size();i++) {
		now=f[now][s[i]-'a'];
		for(int j=now;j&&add[j]!=-1;j=fail[j])
			re+=add[j],add[j]=-1;
	}
	return re;
}

int main() {
	cin>>n;
	for(int i=1;i<=n;i++) {
		cin>>s;
		insert(s);
	}
	build();
	cin>>s;
	cout<<query(s);
	return 0;
}

P5357 【模板】AC 自动机（二次加强版）

code：

#include<bits/stdc++.h>
using namespace std;

const int maxn=2e5+5,maxs=2e5+5;

int n,ch[maxs][26],cnt=0,root=0,num[maxs],fail[maxs],idx[maxn];
string s[maxn],t;
vector<int>edge[maxs];

void insert(string s,int id) {
	int now=root;
	for(int i=0;i<s.size();i++) {
		int c=s[i]-'a';
		if(!ch[now][c]) ch[now][c]=++cnt;
		now=ch[now][c];
	}
	idx[id]=now;
	return ;
}

void build() {
	queue<int>q;
	for(int i=0;i<26;i++)
		if(ch[root][i]) q.push(ch[root][i]),edge[root].push_back(ch[root][i]);
	while(!q.empty()) {
		int now=q.front();
		q.pop();
		for(int i=0;i<26;i++) {
			if(ch[now][i]) {
				fail[ch[now][i]]=ch[fail[now]][i];
				edge[ch[fail[now]][i]].push_back(ch[now][i]);
				q.push(ch[now][i]);
			}
			else ch[now][i]=ch[fail[now]][i];
		}
	}
	return ;
}

void query(string s) {
	int now=root;
	for(int i=0;i<s.size();i++) {
		int c=s[i]-'a';
		now=ch[now][c];
		num[now]++;
	}
	return ;
}

void dfs(int now) {
	for(int i=0;i<edge[now].size();i++)
		dfs(edge[now][i]),num[now]+=num[edge[now][i]];
	return ;
}

int main() {
	cin>>n;
	for(int i=1;i<=n;i++)
		cin>>s[i],insert(s[i],i);
	build();
	cin>>t;
	query(t);
	dfs(root);
	for(int i=1;i<=n;i++)
		cout<<num[idx[i]]<<endl;
	return 0;
}