AC自动机：用来解决多模式串匹配问题。
模式串：要寻找的那个字符串。
AC自动机的本质可以看作KMP+Trie树。KMP构造next数组，目的是为了在每次失配过后，都找到当前仍能匹配的最长长度，针对一个模式串。AC自动机则是对于多个模式串来说，每次失配都找到所有模式串中，还能匹配的最长的部分。在实现方面，通过fail失配指针来实现。
fail指针指向的是当前点代表的前缀子串在所有模式串中的最长后缀。
构造方法：
1.对所有模式串建立字典树。
2.BFS求出fail指针。比较关键的部分是fail[v] = tr[fail[u]][i];这一行代码的意思是，设当前结点的字符为i，则当前结点的fail指针指向其父亲的fail指针的i儿子。
另有一个跳边的优化：若i儿子不存在，tr[u][i] = tr[fail[u]][i];，则直接将该节点的i儿子设为fail指针的i儿子。
P3808 【模板】AC自动机（简单版）
给定(n)个模式串(s_{i})和一个文本串(t)，求有多少个不同的模式串在文本串里出现过。
#include<bits/stdc++.h>
using namespace std;
const int MAXN = 1000005;
inline int read(){
int k = 0, f = 1; char ch = getchar();
while(ch < '0' || ch > '9'){if(ch == '-') f = -1; ch = getchar();}
while(ch >= '0' && ch <= '9'){k = k*10 + ch - '0'; ch = getchar();}
return k * f;
}
int tr[MAXN][26], val[MAXN], fail[MAXN], cnt;
char s[MAXN];
void insert(char *str){
int u = 0;
for(int i = 0; str[i] != ' '; i++){
if(tr[u][str[i] - 'a'] == 0){
tr[u][str[i] - 'a'] = ++cnt;
}
u = tr[u][str[i] - 'a'];
}
val[u]++;
}
void bfs(int u){
queue <int> q;
for(int i = 0; i < 26; i++){
if(tr[0][i]){
fail[tr[0][i]] = 0;
q.push(tr[0][i]);
}
}
while(!q.empty()){
u = q.front(); q.pop();
// printf("u = %d
", u);
for(int i = 0; i < 26; i++){
int v = tr[u][i];
if(v){
fail[v] = tr[fail[u]][i];
q.push(v);
// printf("v = %d, fail = %d
", v, fail[v]);
}
else{ //youhua
tr[u][i] = tr[fail[u]][i];
}
}
}
}
int query(char *str){
int u = 0, ret = 0;
for(int i = 0; str[i] != ' '; i++){
u = tr[u][str[i] - 'a'];
// ret += val[u];
//跳边寻找所有满足条件的模式串
for(int t = u; t != 0 && val[t] != -1; t = fail[t]){
ret += val[t];
val[t] = -1;
}
}
return ret;
}
int main(){
int n = read();
for(int i = 1; i <= n; i++){
scanf("%s", s);
insert(s);
}
// printf("cnt = %d
", cnt);
bfs(0);
// for(int i = 1; i <= cnt; i++){
// printf("fail[%d] = %d
", i, fail[i]);
// }
scanf("%s", s);
int ans = query(s);
printf("%d", ans);
return 0;
}
P3796 【模板】AC自动机（加强版）
同简单版，唯一不同的地方在于统计的方法不一样。
#include<bits/stdc++.h>
using namespace std;
const int MAXN = 1000005;
inline int read(){
int k = 0, f = 1; char ch = getchar();
while(ch < '0' || ch > '9'){if(ch == '-') f = -1; ch = getchar();}
while(ch >= '0' && ch <= '9'){k = k*10 + ch - '0'; ch = getchar();}
return k * f;
}
int tr[MAXN][26], val[MAXN], fail[MAXN], cnt;
int tim[1000];
char s[200][100];
char ch[MAXN];
void insert(char *str, int num){
int u = 0;
for(int i = 0; str[i] != ' '; i++){
if(tr[u][str[i] - 'a'] == 0){
// printf("cnt = %d
", cnt);
// printf("%c, str[i]", str[i]);
tr[u][str[i] - 'a'] = ++cnt;
}
u = tr[u][str[i] - 'a'];
}
val[u] = num;
}
void bfs(int u){
queue <int> q;
for(int i = 0; i < 26; i++){
if(tr[0][i]){
fail[tr[0][i]] = 0;
q.push(tr[0][i]);
}
}
while(!q.empty()){
u = q.front(); q.pop();
for(int i = 0; i < 26; i++){
int v = tr[u][i];
if(v){
fail[v] = tr[fail[u]][i];
q.push(v);
}
else{ //youhua
tr[u][i] = tr[fail[u]][i];
}
}
}
}
void query(char *str){
int u = 0, ret = 0;
for(int i = 0; str[i] != ' '; i++){
u = tr[u][str[i] - 'a'];
for(int t = u; t != 0; t = fail[t]){
if(val[t]){
tim[val[t]]++;
}
}
}
return;
}
int main(){
while(1){
int n = read();
if(n == 0) break;
cnt = 0;
memset(tim, 0, sizeof(tim));
memset(tr, 0, sizeof(tr));
memset(val, 0, sizeof(val));
memset(fail, 0, sizeof(fail));
for(int i = 1; i <= n; i++){
scanf("%s", s[i]);
// printf("%s
", s[i]);
insert(s[i], i);
}
bfs(0);
scanf("%s", ch);
// printf("ch = %s
", ch);
query(ch);
int t = 1;
for(int i = 1; i <= n; i++){
if(tim[t] < tim[i]){
t = i;
}
}
printf("%d
", tim[t]);
for(int i = 1; i <= n; i++){
if(tim[t] == tim[i]){
printf("%s
", s[i]);
}
}
}
return 0;
}
P5357 【模板】AC自动机（二次加强版）
不同点在于可能会出现相同的模式串。这样的话暴力跳fail匹配复杂度最高可以到(n^2)可能会被卡。
解决方法：可以发现每个结点的fail边构成了一颗树。由于每次跳fail边都会跳到不能再跳为止，因此每次到一个点，都会对该点到根的路径上每一个点有贡献。因此采用拓扑排序，从叶结点开始累加答案，这样避免了暴力跳边。
#include<bits/stdc++.h>
using namespace std;
const int MAXN = 2000005;
inline int read(){
int k = 0, f = 1; char ch = getchar();
while(ch < '0' || ch > '9'){if(ch == '-') f = -1; ch = getchar();}
while(ch >= '0' && ch <= '9'){k = k*10 + ch - '0'; ch = getchar();}
return k * f;
}
int tr[MAXN][26], val[MAXN], fail[MAXN], cnt;
int tim[MAXN], pos[MAXN];
//int flag[MAXN];
int du[MAXN];
char s[MAXN];
int vis[MAXN];
queue <int> q;
void insert(char *str, int num){
int u = 0;
for(int i = 0; str[i] != ' '; i++){
if(tr[u][str[i] - 'a'] == 0){
tr[u][str[i] - 'a'] = ++cnt;
}
u = tr[u][str[i] - 'a'];
}
pos[num] = u;
if(!val[u]){
val[u] = num;
}
}
void bfs(int u){
while(!q.empty()) q.pop();
for(int i = 0; i < 26; i++){
if(tr[0][i]){
fail[tr[0][i]] = 0;
q.push(tr[0][i]);
}
}
while(!q.empty()){
u = q.front(); q.pop();
for(int i = 0; i < 26; i++){
int v = tr[u][i];
if(v){
fail[v] = tr[fail[u]][i];
du[fail[v]]++;//
q.push(v);
}
else{ //youhua
tr[u][i] = tr[fail[u]][i];
}
}
}
}
void query(char *str){
int u = 0;
for(int i = 0; str[i] != ' '; i++){
u = tr[u][str[i] - 'a'];
tim[u]++;
}
return;
}
int main(){
// freopen("out.txt", "r", stdin);
// freopen("out1.txt", "w", stdout);
int n = read();
for(int i = 1; i <= n; i++){
scanf("%s", s);
insert(s, i);
}
bfs(0);
scanf("%s", s);
query(s);
// for(int i = 1; i <= n; i++){
// int u = pos[i];
// if(flag[u]) continue;
// for(int t = fail[u]; t != 0; t = fail[t]){
// if(val[t]){
// du[t]++;
// break;
// }
// }
// flag[u] = 1;
// }
// for(int i = 1; i <= cnt; i++){
// printf("du = %d
", du[i]);
// }
while(!q.empty()) q.pop();
for(int i = 1; i <= cnt; i++){
if(du[i] == 0){
q.push(i);
}
}
while(!q.empty()){
int u = q.front(); q.pop();
int v = fail[u];
tim[v] += tim[u];
// vis[val[u]] = tim[u];
du[v]--;
if(du[v] == 0){
q.push(v);
}
}
for(int i = 1; i <= n; i++){
printf("%d
", tim[pos[i]]);
}
return 0;
}