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