前言
在学习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;
}