1、概述

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

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

主串T，n=strlen（T）。

模式串P_i m_i = strlen(p_i)

是O（mn）的時間復雜度。

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

2、 AC算法思想

AC算法思想：用多模式串建立一個確定性的樹形有限狀態機，以主串作為該有限狀態機的輸入，使狀態機進行狀態的轉換，當到達某些特定的狀態時，說明發生模式匹配。

下圖是多模式he/ she/ his /hers構成的一個確定性有限狀態機，做幾點說明：

1、 該狀態機優先按照實線標注的狀態轉換路徑進行轉換，當所有實線標注的狀態轉換路徑條件不能滿足時，按照虛線的狀態轉換路徑進行狀態轉換。如：狀態0時，當輸入h，則轉換到狀態1；輸入s，則轉換到狀態3；否則轉換到狀態0。

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

3、  當狀態轉移到2，5，7，9等紅色狀態點時，說明發生了模式匹配。

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

定義：

在預處理階段，AC自動機算法建立了三個函數，轉向函數goto，失效函數failure和輸出函數output，由此構造了一個樹型有限自動機。

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

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

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

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

f(9)=3。

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

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

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

例：

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

轉向函數：

失效函數：

輸出函數：

3、 AC代碼分析

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

3.1數據結構分析

所有狀態都被存儲在一個ACSM_STATETABLE類型的數組中。

typedef struct  {   

    int      NextState[ ALPHABET_SIZE ]; 

    int      FailState;  

    ACSM_PATTERN *MatchList；

}ACSM_STATETABLE；

NextState對應轉向函數；FailState對應失效函數；MatchList對應輸出函數。

3.2代碼分析

代碼流程如下圖：