一、原理
AC自動機首先將模式組記錄為Trie字典樹的形式，以節(jié)點表示不同狀態(tài)，邊上標以字母表中的字符，表示狀態(tài)的轉(zhuǎn)移。根節(jié)點狀態(tài)記為0狀態(tài)，表示起始狀態(tài)。當一個狀態(tài)處有一個模式串終結(jié)則標記一下。
目前流傳較多的講解多大同小異，尤其是配圖，基本采用的是Aho和Corasiek兩位巨巨的文章efficient string matching an aid to bibliographic search里的，竊以為那張示意圖存在失配點靠前的特點（什么是失配？往下看），看起來稍稍費勁。
我找了樣例畫了一套新圖，主要目標是通過稍微的夸張（失配點遠離）讓過程更清晰。
匹配的過程是：從0狀態(tài)起點開始，以字符流輸入，進行適當?shù)臓顟B(tài)轉(zhuǎn)移，如果可以抵達某一標記終結(jié)的狀態(tài)，則成功匹配模式，串值為從0到終結(jié)點的路徑。
按照傳統(tǒng)的說法，狀態(tài)機有三個主要函數(shù)支撐：goto（狀態(tài)正常轉(zhuǎn)移），fail（狀態(tài)失配轉(zhuǎn)移），output（傳回匹配結(jié)果），而我認為與其規(guī)定是具體的函數(shù)，倒不如說是三個功能的模塊，有不同于函數(shù)的實現(xiàn)形式。
