ac自动机
ac自动机的本质就是对于模式串建个图，然后在用文本串通过kmp的方式跑一边，最后返回匹配数。
图是trie树，百度可以看到这种结构的优点。
需要说一下的是match返回最近的一个trie树上的终止节点，非常方便，不用一个一个fail跳
这是KMP没有的
大抵就是这样
下面的代码cur指当前节点
//2020 1 21&2020 2 16
#include<bits/stdc++.h>
#include<queue>
#define LETTER 26
using namespace std;
struct Trie{
int num,match,fail; //num当此节点为终止节点时数值为一，match指距这个点最近的终止节点的编号，fail同kmp
int next[LETTER];//指在trie树中此节点的某字母边指向的节点
}pool[500001];
Trie* const trie=pool + 1; //trie就是pool，统一将下标减一（有-1下标）
int cnt;
void init(){
cnt=0;
memset(pool, 0,2*sizeof(Trie));
trie[0].fail=-1;
}
queue<int> q;
void build() //构建trie树，过程维护队列中的节点都已处理完成match与fail
{
q.push(0);
while (!q.empty()){
int t=q.front();
q.pop();
for (int i=0;i<LETTER;i++){
int &cur=trie[t].next[i];
if (cur){
q.push(cur);
trie[cur].fail=trie[trie[t].fail].next[i];
trie[cur].match=trie[cur].num!=0 ? cur : trie[trie[cur].fail].match; //当这个点为终止节点时，返回自己，否则返回fail的match
}
else cur=trie[trie[t].fail].next[i]; //如此点无i边，则i边指向fail的i边，fail肯定比此节点浅故按bfs搜索顺序必定以处理完成
}
}
}
int search(string s)
{
int ret=0, cur=0;
for (int i=0;s[i];i++){
cur=trie[cur].next[s[i]-'a'];
for (int temp=trie[cur].match;temp>0;temp=trie[trie[temp].fail].match){ //反复横跳寻找终止节点
ret += trie[temp].num;
}
}
return ret;
}
string str,st[100007];
int main()
{
int n;
cin>>n;
init();
for(int i=1;i<=n;i++){
cin>>st[i];
int len=st[i].size()-1;
int last=0;
for(int j=0;j<=len;++j){
if(trie[last].next[int(st[i][j]-'a')]==0){
trie[last].next[int(st[i][j]-'a')]=++cnt;
last=cnt;
}
else last=trie[last].next[int(st[i][j]-'a')];
if(j==len){
trie[last].num=1;
}
}
}
build();
/*
for(int i=0;i<=cnt;i++){
cout<<"No."<<i<<" failed:"<<trie[i].fail<<" match:"<<trie[i].match<<" num:"<<trie[i].num<<" "<<trie[i].next[0]<<endl;
}
*/
cin>>str;
cout<<search(str)<<endl;
return 0;
}
/*
注：
此代码用于求 所有的模式串在主串中出现的总共次数
*/
/*
3
aabaa
aaa
aba
aaabaa
----------
3
*/
简单的附上例题传送
#include<iostream>
#include<string.h>
#include<cstdio>
#include<stdlib.h>
#include<iomanip>
#include<queue>
#define LETTER 26
using namespace std;
struct Trie{
int num,match,fail;
int next[LETTER];
}pool[1000007];
Trie* const trie=pool + 1;
int cnt;
void init(){
cnt=0;
memset(pool, 0,2*sizeof(Trie));
trie[0].fail=-1;
}
queue<int> q;
void build()
{
q.push(0);
while (!q.empty()){
int t=q.front();
q.pop();
for (int i=0;i<LETTER;i++){
int &cur=trie[t].next[i];
if (cur){
q.push(cur);
trie[cur].fail=trie[trie[t].fail].next[i];
trie[cur].match=trie[cur].num!=0 ? cur : trie[trie[cur].fail].match;
}
else cur=trie[trie[t].fail].next[i];
}
}
}
int search(string s)
{
int ret=0, cur=0;
for (int i=0;s[i];i++){
cur=trie[cur].next[s[i]-'a'];
for (int temp=trie[cur].match;temp>0;temp=trie[trie[temp].fail].match){
ret += trie[temp].num;
trie[temp].num=0;
}
}
return ret;
}
string str,st[1000007];
int main()
{
int n;
cin>>n;
init();
for(int i=1;i<=n;i++){
cin>>st[i];
int len=st[i].size()-1;
int last=0;
for(int j=0;j<=len;++j){
if(trie[last].next[int(st[i][j]-'a')]==0){
trie[last].next[int(st[i][j]-'a')]=++cnt;
last=cnt;
}
else last=trie[last].next[int(st[i][j]-'a')];
if(j==len){
trie[last].num+=1;
}
}
}
build();
cin>>str;
cout<<search(str)<<endl;
return 0;
}