听到AC自动机很多人第一次听到的反应往往是很兴奋的。但其实并不是你们想的那种东西。它的全称是Aho-Corasick algorithm，另外，自动机的英文是Automaton，所以AC自动机即 AC Automaton。为了解释这个算法，首先我们来回顾KMP，你需要很理解KMP的原理，不然看后面的内容就会变得妙不可读。
KMP自动机 本质上KMP其实就是一种自动机。这次我们改用自动机的形式来理解。所谓自动机，一般指的是确定有限状态自动机，你可以看作一个黑箱，每次输入一个数据，它就会改变它的内部状态，并有相应的输出。如果你知道Trie，那么它其实就是一个典型的自动机。我们还是拿字符串abacabab作为例子，如果是生成next数组，结果如下：
string a b a c a b a b \0 next -1 0 0 1 0 1 2 3 2 为了方便变成自动机的方式理解，我们把这个改成有向图
graph LR; linkStyle default interpolate basis 0[Start]--a-->00[1] 00--b-->1[2] 1--a-->2[3] 2--c-->3[4] 3--a-->4[5] 4--b-->5[6] 5--a-->6[7] 6--b-->7[8] 00-.->0 1-.->0 2-.->00 3-.->0 4-.->00 5-.->1 6-.->2 %%7[b]-.->3[c] style 0 fill:#f9f,stroke-dasharray: 5, 5 style 7 fill:#f9f,stroke-dasharray: 5, 5