AC自动机（Aho-Corasick\ automaton），可以解决多模板串匹配的问题。可以理解为可以一次性匹配很多串的KMP。在KMP中，有一个失配函数next，在AC自动机中，也有一个类似的失配函数fail。类似于KMP的转移，每当AC自动机失配时，也会相应地转到当前节点的fail。

Trie

为了一次性高效地匹配字符串，我们需要用一个数据结构来维护所有的模板串。这个数据结构就叫Trie。可以把Trie叫做字典树，所以Trie是一棵树。比如下面这个

Trie

这个就是一棵包含ab,abc,bd,dda四个串的Trie。通过观察，我们可以发现

1. 根节点不包含字符

2. 从根节点到某个节点简单路径上的字母即是这个节点代表的串

3. 串的终点有标记

每次匹配，我们从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];
    }
}