在模式比對問題中，如果模闆有很多個,KMP算法就不太适合了。因為每次查找一個模闆。都要周遊整個文本串。可不可以隻周遊一次文本串呢？可以，方法是把所有模闆組成一個大的狀态轉移圖（稱為$Aho-Corasick$自動機，簡稱$AC$自動機），而不是每個模闆各建一個狀态轉移圖。注意到KMP的狀态轉移圖是線性的字元串加上失配邊組成的，不難想到AC自動機是Trie加上失配邊組成的。
下圖是$\{he,she,his,hers \}$的Trie。
下圖是對應的Aho-Corasick自動機。
如果已經構造好AC自動機，比對算法幾乎和KMP是一樣的，代碼如下：
其中print函數為：
代碼中出現了一個陌生的數組last，下面解釋以下。和Trie一樣，我們認為所有val[j]>0的結點都是單詞結點，反之亦然。但和Trie不同的是，同一個結點可能對應多個字元串的結尾，如圖所示：
結點B不僅意味着找到串101，還意味着找到串01。換句話說，當找到一個模闆後，應該順着失配指針往回走，，看看有沒有其它串。當然，失配指針不一定指向一個單詞結點（比如，兩個串是101和010，那麼上圖的結點A不是單詞結點），為了提高效率，這裡增設一個指針last[j]，表示結點j沿着失配指針往回走時，遇到的下一個單詞結點編号。這個last[j]在正規文獻中叫字尾連結(suffix link)。
計算失配函數的方式和KMP很接近，隻是把線性遞歸改成了按照BFS順序遞推，代碼如下：
由于失配工程比較複雜，要反複沿着失配邊走，在實踐中常常會把上述AC自動機改造一下，把所有不存在的邊補上，即把計算失配函數中的語句"<code>if(!u) continue;</code>"改成：<code>if(!u){ ch[r][c] = ch[f[r]][c]; continue;}</code>
這樣，就完全不需要失配函數了，而是對所有的轉移一視同仁也就是說，find函數中的語句<code>"while(j && !ch[j][c]) j=f[j];"</code>; 可以直接完全删除。
個性簽名：時間會解決一切