1、概述

Aho-Corasick自動機算法（簡稱AC自動機）1975年產(chǎn)生于貝爾實驗室。該算法應(yīng)用有限自動機巧妙地將字符比較轉(zhuǎn)化為了狀態(tài)轉(zhuǎn)移。此算法有兩個特點，一個是掃描文本時完全不需要回溯，另一個是時間復(fù)雜度為O(n)，時間復(fù)雜度與關(guān)鍵字的數(shù)目和長度無關(guān)。

好了，我們先看下最原始的多模式匹配算法：

主串T，n=strlen（T）。

模式串P_i m_i = strlen(p_i)

是O（mn）的時間復(fù)雜度。

上面的算法很笨吧，下面看看聰明的AC算法是個啥意思。

2、 AC算法思想

AC算法思想：用多模式串建立一個確定性的樹形有限狀態(tài)機，以主串作為該有限狀態(tài)機的輸入，使?fàn)顟B(tài)機進行狀態(tài)的轉(zhuǎn)換，當(dāng)?shù)竭_某些特定的狀態(tài)時，說明發(fā)生模式匹配。

下圖是多模式he/ she/ his /hers構(gòu)成的一個確定性有限狀態(tài)機，做幾點說明：

1、 該狀態(tài)機優(yōu)先按照實線標(biāo)注的狀態(tài)轉(zhuǎn)換路徑進行轉(zhuǎn)換，當(dāng)所有實線標(biāo)注的狀態(tài)轉(zhuǎn)換路徑條件不能滿足時，按照虛線的狀態(tài)轉(zhuǎn)換路徑進行狀態(tài)轉(zhuǎn)換。如：狀態(tài)0時，當(dāng)輸入h，則轉(zhuǎn)換到狀態(tài)1；輸入s，則轉(zhuǎn)換到狀態(tài)3；否則轉(zhuǎn)換到狀態(tài)0。

2、 匹配過程如下：從狀態(tài)0開始進行狀態(tài)轉(zhuǎn)換，主串作為輸入。如主串為：ushers，狀態(tài)轉(zhuǎn)換的過程是這樣的：

3、  當(dāng)狀態(tài)轉(zhuǎn)移到2，5，7，9等紅色狀態(tài)點時，說明發(fā)生了模式匹配。

如主串為：ushers，則在狀態(tài)5、2、9等狀態(tài)時發(fā)生模式匹配，匹配的模 式串有she、he、hers。

定義：

在預(yù)處理階段，AC自動機算法建立了三個函數(shù)，轉(zhuǎn)向函數(shù)goto，失效函數(shù)failure和輸出函數(shù)output，由此構(gòu)造了一個樹型有限自動機。

轉(zhuǎn)向函數(shù)，指的是一種狀態(tài)之間的轉(zhuǎn)向關(guān)系。g(pre, x)=next：狀態(tài)pre在輸入一個字符x后轉(zhuǎn)換為狀態(tài)next（上圖中的實線部分）。如果在模式串中不存在這樣的轉(zhuǎn)換，則next=failstate。

失效函數(shù)，指的也是狀態(tài)和狀態(tài)之間一種轉(zhuǎn)向關(guān)系。f(per)=next：是在比較失配的情況下使用的轉(zhuǎn)換關(guān)系。在構(gòu)造轉(zhuǎn)向函數(shù)時，把不存在的轉(zhuǎn)換用failstate表示，但是failstate不是一個具體的狀態(tài)，狀態(tài)機轉(zhuǎn)換轉(zhuǎn)換到failstate狀態(tài)的時候就不知道該往哪轉(zhuǎn)了。所以就要在狀態(tài)機中找到一個有意義的狀態(tài)代替failstate，當(dāng)出現(xiàn)failstate狀態(tài)時，自動切換到那個狀態(tài)。

這個狀態(tài)節(jié)點應(yīng)該具有這樣的特征：從這個狀態(tài)節(jié)點向上直到樹根節(jié)點（狀態(tài)0）所經(jīng)歷的輸入字符，和從產(chǎn)生failstate狀態(tài)的那個狀態(tài)節(jié)點向上所經(jīng)歷的輸入字符串完全相同。而且這個狀態(tài)節(jié)點，是所有具備這些條件的節(jié)點中深度最大的那個節(jié)點。如果不存在滿足條件的狀態(tài)節(jié)點，則失效函數(shù)為0。

累死了。舉例子說吧，對狀態(tài)9輸入任何一個字符都會產(chǎn)生failstate狀態(tài)，需要失效函數(shù)。狀態(tài)3向上到狀態(tài)0經(jīng)過的輸入字符串為s；而由狀態(tài)9向上的輸入字符串為sreh。字符串s相同，并且狀態(tài)3是滿足此條件的唯一節(jié)點，則

f(9)=3。

說來說去，失效函數(shù)就是要干這么件事兒：

意思就是說，在比較模式串1發(fā)生失配時，找一個模式串2，使得P₂[0...j-1] = P₁[i-j+1...i]。然后繼續(xù)比較模式串2?？瓷厦婺莻€圖，想起點兒什么東西沒有？對了，是KMP算法。有人說AC算法就是KMP算法在多模式匹配情況下的擴展。

輸出函數(shù)，指的是狀態(tài)和模式串之間的一種關(guān)系。output(i)={P}，表示當(dāng)狀態(tài)機到達狀態(tài)i時，模式串集合{P}中的所有模式串可能已經(jīng)完成匹配。

例：

模式串為：he/ she/ hers/ his 時，如上圖所示：

轉(zhuǎn)向函數(shù)：

失效函數(shù)：

輸出函數(shù)：

3、 AC代碼分析

下面的代碼參考snort入侵檢測系統(tǒng)開源軟件的acsmx.c文件。

3.1數(shù)據(jù)結(jié)構(gòu)分析

所有狀態(tài)都被存儲在一個ACSM_STATETABLE類型的數(shù)組中。

typedef struct  {   

    int      NextState[ ALPHABET_SIZE ]; 

    int      FailState;  

    ACSM_PATTERN *MatchList；

}ACSM_STATETABLE；

NextState對應(yīng)轉(zhuǎn)向函數(shù)；FailState對應(yīng)失效函數(shù)；MatchList對應(yīng)輸出函數(shù)。

3.2代碼分析

代碼流程如下圖：