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