P3808 AC 自动机（简单版）
大意
求多少个模式串在目标串中出现。
思路
如果说是一对一的匹配，我们可以用 KMP，这倒是好方法，但是对于多个串呢？
那我们尝试用 Trie + KMP 实现一个新的东西，也就是 AC 自动机。
何为 AC 自动机，不能直接 AC 题目，就是专门针对一对多的模式串匹配问题。
具体的做法是这样的，首先先把所有的模式串建成一颗 Trie 树，利用 KMP 的思想对树上的所有节点构建失配指针 fail，对于 Trie 树中的一个节点 \(u\)，它的 fail 指针指向节点 \(v\)，当且仅当：\(v\) 节点所代表的字符串，是 \(u\) 节点所代表的字符串的“最长后缀”。
注意这里的后缀的概念，与 KMP 稍有不同。
至于 fail 指针的构建，这里有一个例子：如果节点 \(u\) 的路径代表字符串 ABCD，我们希望它的 fail 指针指向代表 BCD 的节点；如果 BCD 不存在，就指向 CD；以此类推，直到指向空串（根节点）。
具体来说是这样的：
- 如果子节点 \(v\) 存在：\(v\) 的 fail 指针 \(= u\) 的 fail 指针所指向节点的对应字符 \(i\) 的子节点。
- 如果子节点 \(v\) 不存在：为了优化，我们直接让 \(u\) 的子节点 \(i\) 指向 \(fail[u]\) 的子节点 \(i\)。
这是构建的动图过程。
代码
#include<iostream>
#include<queue>
using namespace std;const int MAXN = 1e6 + 5;
int ch[MAXN][26], cnt[MAXN], idx = 0;
int fail[MAXN], n;
char c[MAXN];void Insert(char *s){int now = 0;for(int i = 0;s[i];i ++){int x = s[i] - 'a';if(!ch[now][x]){ch[now][x] = ++idx;}now = ch[now][x];}cnt[now] ++;
}void build(){queue<int> q;for(int i = 0;i < 26;i ++){if(ch[0][i]){q.push(ch[0][i]);}}while(!q.empty()){int u = q.front(); q.pop();for(int i = 0;i < 26;i ++){if(ch[u][i]){fail[ch[u][i]] = ch[fail[u]][i];q.push(ch[u][i]);}else ch[u][i] = ch[fail[u]][i];}}
}int query(char *s){int res = 0, now = 0;for(int k = 0;s[k];k ++){now = ch[now][s[k] - 'a'];for(int v = now;v && cnt[v] != -1;v = fail[v]){res += cnt[v];cnt[v] = -1;}}return res;
}int main(){cin >> n;for(int i = 1;i <= n;i ++){cin >> c;Insert(c);}build();cin >> c;cout << query(c) << '\n';return 0;
}