簡介
Aho-Corasick算法簡稱AC算法，通過將模式串預(yù)處理為確定有限狀態(tài)自動機(jī)功炮，掃描文本一遍就能結(jié)束筷弦。其復(fù)雜度為O(n)肋演，即與模式串的數(shù)量和長度無關(guān)。
思想
自動機(jī)按照文本字符順序烂琴，接受字符爹殊，并發(fā)生狀態(tài)轉(zhuǎn)移。這些狀態(tài)緩存了“按照字符轉(zhuǎn)移成功（但不是模式串的結(jié)尾）”监右、“按照字符轉(zhuǎn)移成功（是模式串的結(jié)尾）”边灭、“按照字符轉(zhuǎn)移失敗”三種情況下的跳轉(zhuǎn)與輸出情況异希，因而降低了復(fù)雜度健盒。
基本構(gòu)造
AC算法中有三個核心函數(shù)，分別是：
success; 成功轉(zhuǎn)移到另一個狀態(tài)（也稱goto表或success表）
failure; 不可順著字符串跳轉(zhuǎn)的話称簿，則跳轉(zhuǎn)到一個特定的節(jié)點(diǎn)（也稱failure表）扣癣，從根節(jié)點(diǎn)到這個特定的節(jié)點(diǎn)的路徑恰好是失敗前的文本的一部分。
emits; 命中一個模式串（也稱output表）
舉例
以經(jīng)典的ushers為例憨降，模式串是he/ she/ his /hers父虑，文本為“ushers”。構(gòu)建的自動機(jī)如圖
其實(shí)上圖省略了到根節(jié)點(diǎn)的fail邊授药，完整的自動機(jī)如下圖：
匹配過程
自動機(jī)從根節(jié)點(diǎn)0出發(fā)
首先嘗試按success表轉(zhuǎn)移（圖中實(shí)線）士嚎。按照文本的指示轉(zhuǎn)移呜魄，也就是接收一個u。此時success表中并沒有相應(yīng)路線莱衩，轉(zhuǎn)移失敗爵嗅。
失敗了則按照failure表回去（圖中虛線）。按照文本指示笨蚁，這次接收一個s睹晒，轉(zhuǎn)移到狀態(tài)3。
成功了繼續(xù)按success表轉(zhuǎn)移括细，直到失敗跳轉(zhuǎn)步驟2伪很，或者遇到output表中標(biāo)明的“可輸出狀態(tài)”（圖中紅色狀態(tài)）。此時輸出匹配到的模式串奋单，然后將此狀態(tài)視作普通的狀態(tài)繼續(xù)轉(zhuǎn)移锉试。
算法高效之處在于，當(dāng)自動機(jī)接受了“ushe”之后览濒，再接受一個r會導(dǎo)致無法按照success表轉(zhuǎn)移键痛，此時自動機(jī)會聰明地按照failure表轉(zhuǎn)移到2號狀態(tài)，并經(jīng)過幾次轉(zhuǎn)移后輸出“hers”匾七。來到2號狀態(tài)的路不止一條絮短，從根節(jié)點(diǎn)一路往下，“h→e”也可以到達(dá)昨忆。而這個“he”恰好是“ushe”的結(jié)尾丁频，狀態(tài)機(jī)就仿佛是壓根就沒失敗過（沒有接受r），也沒有接受過中間的字符“us”邑贴，直接就從初始狀態(tài)按照“he”的路徑走過來一樣（到達(dá)同一節(jié)點(diǎn)席里，狀態(tài)完全相同）。
構(gòu)造過程
看來這三個表很厲害拢驾，不過奖磁，它們是怎么計算出來的呢？
goto表
很簡單繁疤，了解一點(diǎn)trie樹知識的話就能一眼看穿咖为，goto表就是一棵trie樹。把上圖的虛線去掉稠腊，實(shí)線部分就是一棵trie樹了躁染。
output表
output表也很簡單，與trie樹里面代表這個節(jié)點(diǎn)是否是單詞結(jié)尾的結(jié)構(gòu)很像架忌。不過trie樹只有葉節(jié)點(diǎn)才有“output”吞彤，并且一個葉節(jié)點(diǎn)只有一個output。下圖卻違背了這兩點(diǎn)，這是為什么呢饰恕？其實(shí)下圖的output會在建立failure表的時候進(jìn)行一次拓充挠羔。
以上兩個表通過一個dfs就可以構(gòu)造出來。關(guān)于trie樹的更詳細(xì)內(nèi)容埋嵌，請參考：《Ansj分詞雙數(shù)組Trie樹實(shí)現(xiàn)與arrays.dic詞典格式》褥赊，《Trie樹分詞》，《雙數(shù)組Trie樹(DoubleArrayTrie)Java實(shí)現(xiàn)》莉恼。
failure表
這個表是trie樹沒有的拌喉，加了這個表，AC自動機(jī)就看起來不像一棵樹俐银，而像一個圖了尿背。failure表是狀態(tài)與狀態(tài)的一對一關(guān)系，別看圖中虛線亂糟糟的捶惜，不過你仔細(xì)看看田藐，就會發(fā)現(xiàn)節(jié)點(diǎn)只會發(fā)出一條虛線，它們嚴(yán)格一對一吱七。
這個表的構(gòu)造方法是：
首先規(guī)定與狀態(tài)0距離為1（即深度為1）的所有狀態(tài)的fail值都為0汽久。
然后設(shè)當(dāng)前狀態(tài)是S1，求fail(S1)踊餐。我們知道景醇，S1的前一狀態(tài)必定是唯一的（剛才說的一對一），設(shè)S1的前一狀態(tài)是S2吝岭，S2轉(zhuǎn)換到S1的條件為接受字符C三痰，測試S3= goto(fail(S2), C)。
如果成功窜管，則fail(S1) = goto(fail(S2), C) =?S3散劫。
如果不成功，繼續(xù)測試S4= goto(fail(S3), C)是否成功幕帆，如此重復(fù)获搏，直到轉(zhuǎn)換到某個有效的狀態(tài)Sn，令fail(S1) =?Sn失乾。
Java實(shí)現(xiàn)
原理誰都可以說幾句的常熙，可是優(yōu)雅健壯的代碼卻不是那么容易寫的。我考察了Git上幾個AC算法的實(shí)現(xiàn)仗扬，發(fā)現(xiàn)robert-bor的實(shí)現(xiàn)非常好症概。一趟代碼看下來蕾额，學(xué)到了不少設(shè)計上的知識早芭。我fork了下來，針對Ascii做了優(yōu)化诅蝶，添加了中文注釋退个。
另外募壕，我實(shí)現(xiàn)了基于雙數(shù)組Trie樹的AC自動機(jī)：《Aho Corasick自動機(jī)結(jié)合DoubleArrayTrie極速多模式匹配》。性能更高语盈，內(nèi)存可控舱馅。
```
//創(chuàng)建set集合
Set stringSet =new HashSet<>();
stringSet.add("高危");
stringSet.add("并發(fā)");
stringSet.add("江蘇");
stringSet.add("彩信");
String[] value =new String[stringSet.size()];
stringSet.toArray(value);
Trie.TrieBuilder trieBuilder = Trie.builder();
if(false){
trieBuilder.stopOnHit();
}
for (String key:value) {
trieBuilder.addKeyword(key);
}
Trie trie = trieBuilder.build();
System.out.println("查看是否包含這些字樣");
System.out.println(trie.containsMatch("江蘇高危短信彩信錫"));
System.out.println("----------查看有哪些-----------------");
Collection emits = trie.parseText("江蘇高危短信彩信錫");
for(Emit temp : emits)
{
System.out.println("包含集合："+temp.getKeyword());
}
```
