AC自动机
AC自动机（Aho-Corasick\ automaton），可以解决多模板串匹配的问题。可以理解为可以一次性匹配很多串的KMP。在KMP中，有一个失配函数next，在AC自动机中，也有一个类似的失配函数fail。类似于KMP的转移，每当AC自动机失配时，也会相应地转到当前节点的fail。
Trie
为了一次性高效地匹配字符串，我们需要用一个数据结构来维护所有的模板串。这个数据结构就叫Trie。可以把Trie叫做字典树，所以Trie是一棵树。比如下面这个
Trie
这个就是一棵包含ab,abc,bd,dda四个串的Trie。通过观察，我们可以发现
-
根节点不包含字符
-
从根节点到某个节点简单路径上的字母即是这个节点代表的串
-
串的终点有标记
每次匹配，我们从Trie的根节点出发，尝试用文本串去匹配Trie树，由于Trie树将一些字符串压缩到了一起，因此时间复杂度会大大降低。但注意，Trie树是一种用空间换时间的做法
部分代码：
void init() {memset(trie[0],0,sizeof(trie[0])),ncnt=0;}
void insert(char s[],int len,int n) {//插入新串
int now=0,c;
for (int i=1;i<=len;i++) {//查找路径（没有则添加）
c=idx(s[i]);
if (trie[now][c]==0)
now=trie[now][c]=++ncnt,memset(trie[now],0,sizeof(trie[now]));
else now=trie[now][c];
}
val[now]=n;//标记终点
}
Trie树的空间复杂度是O(nmt)，n是串的总数，m是最长串的长度，t是节点字母的种类
AC自动机实现
我们引入一个新的数组last，代表与当前节点有最长后缀的串在Trie上的编号。很明显，假如当前串匹配成功了，那么它的last也一定可以匹配成功（是它的后缀啊）
last的一个重要性质： 设p的失败指针指向节点k，则它应该满足这样的性质：从root到k的字符串完全匹配于从p往上相同长度的后缀
注意last与fail的区别：last是指当前节点的某个出现在模板串之中的后缀，而fail则不要求出现在模板串中
如果当前串匹配失败，那么就一直跳fail。我们这样考虑：
假设s[1,i]已经匹配成功了，第i个字符对应Trie上的u号节点，但是s[i+1]匹配失败了，很明显，我们可以从u节点跳到它的
fail。因为s[1,i]已经匹配成功了，那么s[1,i]的某个后缀（对应fail）也一定可以匹配成功
int c=idx(s[i]);
while (now&&!trie[now][c]) now=fail[now];
举个例子
我们考虑这样一个自动机
AC自动机
这是一棵倒着的Trie加上一些虚线箭头一个AC自动机的状态图，绿色的点代表有标记。至于点上的数，可以暂时不管。
实线代表Trie上的边，虚线代表fail指向的节点
观察91这个点，它表示的串是SHE，它的fail指针指向76号点，这个点表示的串是HE，可以发现，它是SHE的一个后缀。
我们考虑在这样一棵Trie上匹配串SHERS
1.当前位于根节点，对应字符S，因此走85号点，匹配成功
2.当前位于85号点，对应字符H，因此走90号点，匹配成功
3.当前位于90号点，对应字符E，因此走91号点，匹配成功
4.91号点被标记过，匹配数+1
5.当前位于91号点，对应字符R，这个点没有字符为R的点，匹配失败，跳到91号点的fail指针76号点
6.当前位于76号点，对应字符R，因此走160号点，匹配成功
7.当前位于160号点，对应字符S，因此走86号点，匹配成功
8.至此，串SHERS已匹配完成
代码实现如下
void query(char s[],int len) {
int now=0;
for (int i=1;i<=len;i++) {
int c=idx(s[i]);
while (now&&!trie[now][c]) now=fail[now];//匹配失败，则一直跳fail指针
now=trie[now][c];
if (val[now]) cnt[val[now]]++;//匹配成功，且当前节点是某个模板串的末尾
int las=last[now];
while (val[las]) val[las]=0,cnt[val[las]]++,las=last[las];//当前节点匹配成功，它的last也一定匹配成功
}
}
接下来是AC自动机的关键部分，即预处理fail指针与last指针
由于一个节点的fail的深度一定小于这个点的深度，所以我们考虑用bfs实现
考虑从一个已经求出fail与last的节点now转移到他的后继节点son
如果now的fail指针有与son相同的后继节点，那么直接转移到那个后继节点。否则一直跳fail，直到根节点。
for (int i=0;i<128;i++)
if (trie[now][i]) {
int f=fail[now];
while (f&&!trie[f][i]) f=fail[f];
int son=trie[now][i];
fail[son]=trie[f][i];
}
如果now节点所指向的fail的这个儿子已经被标记过，即是某个模板串的结尾，就直接将其赋到son，否则一直跳last
last[son]=val[fail[son]]?fail[son]:last[fail[son]];
总bfs实现如下
void bfs() {
queue<int> q;
while (!q.empty()) q.pop();
fail[0]=last[0]=0;
for (int i=0;i<26;i++) {
int now=trie[0][i];
if (now) fail[now]=last[now]=0,q.push(now);
}
while (!q.empty()) {
int now=q.front();q.pop();
for (int i=0;i<26;i++)
if (trie[now][i]) {
int f=fail[now];
while (f&&!trie[f][i]) f=fail[f];
int son=trie[now][i];
fail[son]=trie[f][i],last[son]=val[fail[son]]?fail[son]:last[fail[son]];
q.push(son);
}
}
}
最后是AC自动机模板代码
int ncnt=0,trie[100010][26],val[100010];
int idx(char c) {return c-'a';}
void init() {memset(trie[0],0,sizeof(trie[0])),ncnt=0;}
void insert(char s[],int len,int n) {
int now=0,c;
for (int i=1;i<=len;i++) {
c=idx(s[i]);
if (trie[now][c]==0)
now=trie[now][c]=++ncnt,memset(trie[now],0,sizeof(trie[now]));
else now=trie[now][c];
}
val[now]=n;//val里存的是串的编号
}
int fail[100010],last[100010];
void bfs() {
queue<int> q;
while (!q.empty()) q.pop();
fail[0]=last[0]=0;
for (int i=0;i<26;i++) {
int now=trie[0][i];
if (now) fail[now]=last[now]=0,q.push(now);
}
while (!q.empty()) {
int now=q.front();q.pop();
for (int i=0;i<26;i++)
if (trie[now][i]) {
int f=fail[now];
while (f&&!trie[f][i]) f=fail[f];
int son=trie[now][i];
fail[son]=trie[f][i],last[son]=val[fail[son]]?fail[son]:last[fail[son]];
q.push(son);
}
}
}
int cnt[510];
void query(char s[],int len) {
int now=0;
for (int i=1;i<=len;i++) {
int c=idx(s[i]);
while (now&&!trie[now][c]) now=fail[now];
now=trie[now][c];
if (val[now]) cnt[val[now]]++;
int las=last[now];
while (val[las]) val[las]=0,cnt[val[las]]++,las=last[las];
}
}
