例题来自于ACWing网站
一、关于AC自动机
AC自动机=KMP查找算法+Tire字典树 —>可优化为Trie图
KMP查找算法：
思路：
例题：
给定一个模式串 SS，以及一个模板串 PP，所有字符串中只包含大小写英文字母以及阿拉伯数字。
模板串 PP 在模式串 SS 中多次作为子串出现。
求出模板串 PP 在模式串 SS 中所有出现的位置的起始下标。
输入格式
第一行输入整数 NN，表示字符串 PP 的长度。
第二行输入字符串 PP。
第三行输入整数 MM，表示字符串 SS 的长度。
第四行输入字符串 SS。
输出格式
共一行，输出所有出现位置的起始下标（下标从 00 开始计数），整数之间用空格隔开。
数据范围
1≤N≤1051≤N≤105
1≤M≤1061≤M≤106
输入样例：
3
aba
5
ababa输出样例：
0 2代码实现：
#include
using namespace std;
const int N = 100010, M = 1000010;
int n, m;
int ne[N]; //next数组
char s[M], p[N];
int main()
{
cin >> n >> p + 1 >> m >> s + 1; // 字符串从1开始
// 求next数组
for (int i = 2, j = 0; i <= n; i ++ )
{
while (j && p[i] != p[j + 1]) j = ne[j]; // 后退到next[j]
if (p[i] == p[j + 1]) j ++ ;
ne[i] = j; // 记录过程
}
// 匹配字符串
for (int i = 1, j = 0; i <= m; i ++ )
{
while (j && s[i] != p[j + 1]) j = ne[j]; // 如果不匹配，退一步到next[j]
if (s[i] == p[j + 1]) j ++ ;
if (j == n) // 匹配成功
{
printf("%d ", i - n); // 输出结果
j = ne[j]; // 匹配成功的逻辑，后退一步
}
}
return 0;
}
模板：
#include
using namespace std;
const int N = 100010, M = 10010; // N为模式串长度，M匹配串长度
int n, m;
int ne[M]; // next[]数组，避免和头文件next冲突
char s[N], p[M]; // s为模式串,p为匹配串
int main()
{
cin >> n >> s+1 >> m >> p+1; // 下标从1开始
// 求next[]数组
for(int i = 2, j = 0; i <= m; i++)
{
while(j && p[i] != p[j+1]) j = ne[j];
if(p[i] == p[j+1]) j++;
ne[i] = j;
}
// 匹配操作
for(int i = 1, j = 0; i <= n; i++)
{
while(j && s[i] != p[j+1]) j = ne[j];
if(s[i] == p[j+1]) j++;
if(j == m) // 满足匹配条件，打印开头下标, 从0开始
{
printf("%d ", i - m); // (若从1开始，加1)
j = ne[j]; // 再次继续匹配
}
}
return 0;
}
Tire字典树：
思路：
例题：
维护一个字符串集合，支持两种操作：
I x向集合中插入一个字符串 xx；Q x询问一个字符串在集合中出现了多少次。
共有 NN 个操作，输入的字符串总长度不超过 105105，字符串仅包含小写英文字母。
输入格式
第一行包含整数 NN，表示操作数。
接下来 NN 行，每行包含一个操作指令，指令为 I x 或 Q x 中的一种。
输出格式
对于每个询问指令 Q x，都要输出一个整数作为结果，表示 xx 在集合中出现的次数。
每个结果占一行。
数据范围
1≤N≤2∗1041≤N≤2∗104
输入样例：
5
I abc
Q abc
Q ab
I ab
Q ab输出样例：
1
0
1二、AC自动机实现
一个常见的例子就是给出n个单词，再给出一段包含m个字符的文章，找出有多少个单词在文章里出现过。
思路：
例题：
给定 nn 个长度不超过 5050 的由小写英文字母组成的单词，以及一篇长为 mm 的文章。
请问，其中有多少个单词在文章中出现了。
注意：每个单词不论在文章中出现多少次，仅累计 11 次。
输入格式
第一行包含整数 TT，表示共有 TT 组测试数据。
对于每组数据，第一行一个整数 nn，接下去 nn 行表示 nn 个单词，最后一行输入一个字符串，表示文章。
输出格式
对于每组数据，输出一个占一行的整数，表示有多少个单词在文章中出现。
数据范围
1≤n≤1041≤n≤104,
1≤m≤1061≤m≤106
输入样例：
1
5
she
he
say
shr
her
yasherhs输出样例：
3代码实现：
#include
#include
#include
using namespace std;
const int N = 10010, S = 55, M = 1000010;
int trie[N * S][26], cnt[N * S], idx; //cnt[i]表示以i + 'a'为结尾的个数 idx为当前树节点的指针
char str[M]; //以"/0"为结尾，所以不用每次都更新
int que[N * S], fail[N * S]; //que[]表示队列 ， fail[]为失配指针(下标表示树节点的指针)
int n;
void insert(){
int p = 0;
for(int i = 0;str[i];++i){
int u = str[i] - 'a';
if(!trie[p][u]) trie[p][u] = ++idx;
p = trie[p][u];
}
cnt[p]++;
}
void build(){ //构造fail数组，bfs
int hh = 0,tt = -1; //队头和队尾指针
//根节点是第0层
for(int i = 0;i < 26;++i){ //第一层的元素全部入队
if(trie[0][i]) que[++tt] = trie[0][i];
}
while(hh <= tt){
int ans = que[hh++];
//枚举当前队头的26个分支
for(int i = 0;i < 26;++i){
if(trie[ans][i]){ //如果存在我们就让它的fail指针指向他父亲节点 a 的 fail 指针指向的那个节点（根）的具有相同字母的子节点
fail[trie[ans][i]] = trie[fail[ans]][i];
que[++tt] = trie[ans][i]; //当前节点入队
}else{ //就算不存在，不跳，他的值等于父节点的fail只想的具有相同字母的子节点
trie[ans][i] = trie[fail[ans]][i];
}
}
}
}
int main(){
int t;
cin >> t;
while(t--){
memset(cnt,0,sizeof cnt);
memset(trie,0,sizeof trie);
memset(fail,0,sizeof fail);
idx = 0;
cin >> n;
for(int i = 0;i < n;++i){
scanf("%s",str);
insert();
}
build();
scanf("%s",str);
int res = 0;
//j记录当前树节点的指针，初始是根节点
for(int i = 0,j = 0;str[i];++i){ //枚举总串str的每一个字母
int u = str[i] - 'a';
j = trie[j][u]; //跳到下一个树节点
int p = j; //每次从当前树节点开始
//fail[p]所指向的树节点如果有结尾标记可以直接算上，因为当前模式串后缀和fail指针指向的模式串部分前缀相同，所以是包含在里面的
while(p){ //假如模式串"she"可以匹配上，那么匹配到"e"的时候，用fail指针跳到模式串"he"的"e"，那么也一定能够匹配"he"
res += cnt[p];
cnt[p] = 0; //去除标记
p = fail[p];
}
}
cout << res << endl;
}
return 0;
} 
