\(Aho-Corasick\) 自动机，简称\(AC\)自动机，适用于模式匹配问题中有多个模板的情况，因为我们所熟知的\((K)MP\)算法每查找一个模板，都需要遍历整个字符串，这样看来，\((K)MP\)对于模式匹配问题中有多个模板的情况的时间开销是非常之大的，为了尽量减少时间开销，我们要做的是只遍历一次字符串，为此，我们需要将所有模板建立成一个大的状态转移图，而不是像\((K)MP\)算法那样将每一个模板各建立一个状态转移图。因为\(KMP\)算法的状态转移图是线性字符串加上失配边构成的，我们不难想到\(AC\)自动机是由\(Trie\)加上失配边组成的。

---

\(AC\)自动机的匹配算法和\(KMP\)算法几乎一样，如下：

void find(char *T)    {        int n=strlen(T);        int j=0;//当前结点编号，初始为根节点(Root)        for(int i=0;i

其中\(print\)函数扩展写法为：

void print(int j)//递归打印以结点j为结尾的所有字符串    {        if(j)            {                printf("%d: %d\n",j,val[j]);                print(last[j]);            }    }

---

相比于\(KMP\)算法，其中出现了一个陌生的数组\(last\)，和\(Trie\)一样，我们认为所有\(val[j]>0\)的节点\(j\)都是单词节点，反之亦然，但与\(Trie\)不同的是，同一个节点可能对应多个字符串的结尾，为了提高效率，增设一个指针\(last[j]\),表示结点\(j\)沿着失配指针向回走时，遇到的下一个单词结点编号。这个\(last[j]\)在正规的文献里叫做后缀链接（\(suffix\) - \(link\)）。

---

计算失配函数的方式同样和\(KMP\)算法很接近，只是把线性递归改为了\(BFS\)顺序递推，如下：

int getFail()    {        queue
    
      q;        f[0]=0;        for(int c=0;c<= SIGMA_SIZE;c++)            {                int u=ch[0][c];                if(u)                    {                        f[u]=0;                        q.push(u);                        last[u]=0;                    }            }        while(!q.empty())            {                int r=q.front();                q.pop();                for(int c=0;c< SIGMA_SIZE;c++)                    {                        int u=ch[r][u];                        if(!u) continue;//如要把所有不存在的边补上，则需改为if(!u) {ch[r][c]=ch[f[r]][c];continue;}                        q.push(u);                        int v=f[r];                        while(v&&ch[v][c]) v=f[v];                        f[u]=ch[v][c];                        last[u]=val[f[u]]?f[u]:last[f[u]];                    }            }    }
    

也就是说，如果要把所有不存在的边补上的话，就完全不需要失配函数，\(find\)函数中的

while(j&&!ch[j][c]) j=f[j]

就可以直接完全删除