AC自动机（Aho-Corasick\ automaton），可以解决多模板串匹配的问题。可以理解为可以一次性匹配很多串的KMP。在KMP中，有一个失配函数next，在AC自动机中，也有一个类似的失配函数fail。类似于KMP的转移，每当AC自动机失配时，也会相应地转到当前节点的fail。
Trie
为了一次性高效地匹配字符串，我们需要用一个数据结构来维护所有的模板串。这个数据结构就叫Trie。可以把Trie叫做字典树，所以Trie是一棵树。比如下面这个
文章图片
Trie 这个就是一棵包含ab,abc,bd,dda四个串的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上的边，虚线代表
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，否则一直跳lastlast[son]=val[fail[son]]?fail[son]:last[fail[son]];
总bfs实现如下
void bfs() {
queue 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自动机】最后是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 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];
}
}
