介绍
AC自动机全称Aho-Corasick automaton，该算法在1975年产生于贝尔实验室，是著名的多模匹配算法。
本质上就是在一颗trie树上跑KMP算法。
实现
首先需要将若干模式字符串插入字典树当中。然后构建fail指针，用于后续匹配模式串。值得注意的是，假设在trie树当前位置是cur，它到根节点路径上的字符串就是当前已经匹配字符串（假设是s1）；再假设fail[cur]指向位置对应的字符串是s2，那么s2就是s1的真后缀。也就是说当前位置fail指针的含义是当前位置对应字符串的真后缀，这一点就和KMP的next数组含义是一样的。如果trie树是一条链（比如只插入了一个模式串），那么fail指针和KMP中的next数组就一模一样了。
如何构造fail指针？按bfs顺序构建。假设构造到位置cur，cur以及cur上层（祖先结点）的fail指针都构建好了。
然后下一个位置是next=tr[cur][ch]，我们需要构建fail[next]。fail的意义是后缀，即要找next位置对应字符串的后缀。
显然，fail[cur]是cur对应的后缀，如果tr[fail[cur]][ch]存在，那么tr[fail[cur]][ch]就是next=tr[cur][ch]的后缀了。即fail[next] = tr[fail[cur]][ch]；否则就找fail[fail[cur]]，相当于缩短后缀，一直跳下去，直到找到为止，或找不到结果为0。
模板的实现用了扩展trie树状态来优化多次跳fail，以使得查询更好写。具体见代码。
值得注意的一些事情
-
板子要点
格式化AC自动机时，trie树要逐层清空，用到多少清空多少（在insert里面清空，同时初始化相应的fail和e（e用于记录结点信息））。否则如果直接全部清空在多组数据的情况下可能会超时。不信试试 The Dominator of Strings -
如果每个模式串仅仅查询一次就删除，那么时间复杂度是大概是所有字符串长度和；但如果不删除，面对极端数据可能达到O(nm)的复杂度，比如像“aaaaaa”这样的数据。因为每次在trie树中每层都要跳很多次。
//AC自动机模板，查询文本中模式串的出现次数。
const int N = 200000;
int tr[N][26]; //N等于所有模式串长度总和
int e[N]; //结点信息
int fail[N]; //fail指针
char s[N];
int si = 0;
namespace AC {
void init() {
memset(tr[0], 0,sizeof tr[0]); //清空trie树第一层，代表这颗树需要重新构建。
si = 0;
}
void insert(char s[]) { //插入同时初始化trie树，提高初始化效率
int cur = 0;
fail[cur] = 0;
e[cur] = 0;
for(int i = 0; s[i]; i++) {
if(tr[cur][s[i] - 'a']) cur = tr[cur][s[i] - 'a'];
else {
tr[cur][s[i] - 'a'] = ++si;
cur = si;
memset(tr[si], 0, sizeof tr[si]);
fail[cur] = 0;
e[cur] = 0;
}
}
e[cur]++; //更新结点信息（这里是出现次数）
}
void build() {
queue<int> q;
for(int i = 0; i < 26; i++)
if(tr[0][i]) q.push(tr[0][i]);
//tr[fail[cur]]代表cur的一个后缀
while(!q.empty()) {
int cur = q.front();
q.pop();
for(int i = 0; i < 26; i++) {
if(tr[cur][i]) {
fail[tr[cur][i]] = tr[fail[cur]][i]; //不用判断tr[fail[cur]][i]是否存在，因为不存在的tr[fail[cur]][i]已经建立好了转跳。
q.push(tr[cur][i]);
} else {
tr[cur][i] = tr[fail[cur]][i]; //扩展trie树，面对不存在的状态，直接转跳到另一个后缀。这样直接无脑在trie上走就可以实现自动失配转跳。
//有点类似路径压缩
}
}
}
}
int query(char s[]) { //返回有多少模式串在s中出现过
int cnt = 0;
int cur = 0;
for(int i = 0; s[i]; i++) {
cur = tr[cur][s[i] - 'a'];
for(int j = cur; j && e[j] != -1; j = fail[j]) { //查询每个后缀是否匹配到了模式串
cnt += e[j];
e[j] = -1; //找到了就可以删掉防止重复查询
}
}
return cnt;
}
}