應用
壹個常見的例子就是給出n個單詞，再給出壹段包含m個字符的文章，讓妳找出有多少個單詞在文章裏出現過。
要搞懂AC自動機，先得有模式樹（字典樹）Trie和KMP模式匹配算法的基礎知識。AC自動機算法分為3步：構造壹棵Trie樹，構造失敗指針和模式匹配過程。
如果妳對KMP算法了解的話，應該知道KMP算法中的next函數（shift函數或者fail函數）是幹什麽用的。KMP中我們用兩個指針i和j分別表示，A[i-j+ 1..i]與B[1..j]完全相等。也就是說，i是不斷增加的，隨著i的增加j相應地變化，且j滿足以A[i]結尾的長度為j的字符串正好匹配B串的前 j個字符，當A[i+1]≠B[j+1]，KMP的策略是調整j的位置（減小j值）使得A[i-j+1..i]與B[1..j]保持匹配且新的B[j+1]恰好與A[i+1]匹配，而next函數恰恰記錄了這個j應該調整到的位置。同樣AC自動機的失敗指針具有同樣的功能，也就是說當我們的模式串在Trie上進行匹配時，如果與當前節點的關鍵字不能繼續匹配，就應該去當前節點的失敗指針所指向的節點繼續進行匹配。