第一次看到這個名字的時候覺得非常高級，深入學習就發(fā)現(xiàn)，AC就是一種多模式字符串匹配算法。前面介紹的BF算法，RK算法，BM算法，KMP算法都屬于單模式匹配算法，而Trie樹是多模式匹配算法，多模式匹配算法就是在一個主串中查找多個模式串，舉個最常用的例子，比如我們在論壇發(fā)表評論或發(fā)帖的時候，一般論壇后臺會檢測我們發(fā)的內(nèi)容是否有敏感詞，如果有敏感詞要么是用***替換，要么是不讓你發(fā)送，我們評論是通常是一段話，這些敏感詞可能成千上萬，如果用每個敏感詞都在評論的內(nèi)容中查找，效率會非常低，AC自動機中，主串會與所有的模式串同時匹配，這時候就可以利用AC自動機這種多模式匹配算法來完成高效的匹配，
一 AC自動機算法原理
AC自動機算法是構(gòu)造一個Trie樹，然后再添加額外的失配指針。這些額外的適配指針準許在查找字符串失敗的時候進行回退（例如在Trie樹種查找單詞bef失敗后，但是在Trie樹種存中bea這個單詞，失配指針會指向前綴be），轉(zhuǎn)向某些前綴分支，免于重復匹配前綴，提高算法效率。
常見于IDS軟件或病毒檢測軟件中病毒特征字符串，可以構(gòu)建AC自動機，在這種情況下，算法的時間復雜度為輸入字符串的長度和匹配數(shù)量之和。
假設(shè)現(xiàn)有模式字符串集合：{abd,abdk, abchijn, chnit, ijabdf, ijaij} 構(gòu)建AC自動機如下：
說明：
- 根節(jié)點不存在任何字符，根節(jié)點的fail指針為null。
- 虛線表示該節(jié)點的fail指針，所有模式串中字符串最后一個字符節(jié)點外面用紅圈表示，說明是匹配上的字符串。
- 每個節(jié)點都有fail指針，為了方便圖中未畫出根節(jié)點的fail虛線。
每個節(jié)點的fail指針表示從根節(jié)點到該節(jié)點所組成字符序列中所有后綴和目標的模式串集合中所有前綴 兩者中最長的公共部分。
舉例：
圖中，從根節(jié)點到目標字符串“ijabdf”中d組成字符序列“ijabd”的所有后綴在整個模式串中：
{abd,abdk, abchijn, chnit, ijabdf, ijaij}的所有前綴中，最長的公共部分就是abd，所以“ijabdf”中d的fail指針就是指向abd中的d。
https://www.cnblogs.com/nullzx/p/7499397.html
二 AC自動機運行過程
1）當前指針curr指向AC自動機的根節(jié)點：curr=root。
2）從文本串中讀?。ㄏ拢┮粋€字符。
3）從當前節(jié)點的所有孩子節(jié)點中尋找與該字符匹配的節(jié)點：
- 如果成功：判斷當前節(jié)點以及當前節(jié)點fail指向的節(jié)點是否表示字符串結(jié)束，則將匹配的字符串（從根節(jié)點到結(jié)束節(jié)點）保存。curr指向孩子節(jié)點，繼續(xù)執(zhí)行步驟2。
- 如果失敗執(zhí)行步驟4
4）若fail == null，則說明沒有任何子串為輸入字符串的前綴，這時設(shè)置curr = root，執(zhí)行步驟2.
若fail != null,則將curr指向 fail節(jié)點，指向步驟3。
理解起來比較復雜，找網(wǎng)上的一個例子，假設(shè)文本串text = “abchnijabdfk”。
查找過程如下：
說明如下：
1）按照字符串順序依次遍歷到：a-->b-->c-->h ,這時候發(fā)現(xiàn)文本串中下一個節(jié)點n和Trie樹中下一個節(jié)點i不匹配，且h的fail指針非空，跳轉(zhuǎn)到Trie樹中ch位置。
注意c-->h的時候判斷h不為結(jié)束節(jié)點，且c的fail指針也不是結(jié)束節(jié)點。
2）再接著遍歷n-->i,發(fā)現(xiàn)i節(jié)點在Trie樹中的下一個節(jié)點找不到j(luò)，且有fail指針，則繼續(xù)遍歷，
遍歷到d的時候要注意，d的下一個匹配節(jié)點f是結(jié)束字符，所以得到匹配字符串：ijabdf，且d的fail節(jié)點也是d，且也是結(jié)束字符，所以得到匹配字符串a(chǎn)bd，不過不是失敗的匹配，所以curr不跳轉(zhuǎn)。
三 AC自動機的構(gòu)造過程
先將目標字符串插入到Trie樹種，然后通過廣度有限遍歷為每個節(jié)點的所有孩子節(jié)點找到正確的fail指針。
具體步驟如下：
1）將根節(jié)點的所有孩子節(jié)點的fail指針指向根節(jié)點，然后將根節(jié)點的所有孩子節(jié)點依次入隊列。
2）若隊列不為空：
2.1）出列一個字符，將出列的節(jié)點記為curr，failTo表示curr的
fail指針，即failTo = curr.fail 。
2.2) 判斷curr.child[i] == failTo.child[i]是不是成立：
成立：curr.child[i].fail = failTo.child[i]
因為當前字符串的后綴和Tire樹的前綴最長部分是到fail，
且子字符和failTo的下一個字符相同，則fail指針就是
failTo.child[i]。
不成立： 判斷failTo是不是為null是否成立：
成立： curr.child[i].fail = root = null。
不成立： failTo = failTo.fail 繼續(xù)2.2
curr.child[i]入列，再次執(zhí)行步驟2）。
3）隊列為空結(jié)束。
四 實例理解
每個結(jié)點的fail指向的解決順序是按照廣度有限遍歷的順序完成的，或者說層序遍歷的順序進行，我們根據(jù)父結(jié)點的fail指針來求當前節(jié)點的fail指針。
理解fail指針的含義：表示從根節(jié)點到該節(jié)點所組成字符序列的所有后綴和 整個模式字符串集合即整個Trie樹中 所有前綴 兩者中的最長公共部分。
上圖為例，我們要解決y節(jié)點的fail指針問題，已經(jīng)知道y節(jié)點的父節(jié)點x1的fail是指向x2的，根據(jù)fail指針的定義，我們知道紅色橢圓中的字符串序列肯定相等，而且是最長的公共部分。依據(jù)y.fail的含義，如果x2的某個孩子節(jié)點和節(jié)點y表示的表示的字符相等，y的fail就指向它。
如果x2的孩子節(jié)點中不存在節(jié)點y表示的字符。由于x2.fail指向x3，根據(jù)x2.fail的含義，我們知道綠色框中的字符序列是相同的。顯然如果x3的某個孩子和節(jié)點y表示字符相等，則y.fail就指向它。
如果x3的孩子節(jié)點不存在節(jié)點y表示的字符，我們重復這個步驟，直到xi的fail節(jié)點指向null，說明我們達到頂層，只要y.fail= root就可以了。
構(gòu)造過程就是知道當前節(jié)點的最長公共前綴的情況下，去確定孩子節(jié)點的最長公共前綴。
4.1 確定圖中h節(jié)點fail指向的過程
下圖中，每個節(jié)點都有fail虛線，指向根節(jié)點的虛線沒畫出，求圖中c的孩子節(jié)點h的fail指向：
原圖中，深藍色的框出來的是已經(jīng)確定fail指針的，求紅色框中h節(jié)點的fail指針。
這時候，我們看下h的父親節(jié)點c的fail指針指向，為ch中的c（這表示abc字符串的所有后綴bc和c和Trie樹的所有前綴中最長公共部分為c），且這個c節(jié)點的孩子節(jié)點中有字符為h的字符，所以圖中紅色框中框出的h節(jié)點的fail指針指向 ch字符串中的h。
4.2 確定圖中i.fail指向
求紅色框中i的fail指針指向，上圖中，我們可以看到i的父親節(jié)點h的指向為ch中的h，（也就是說我們的目標字符串結(jié)合中所有前綴和字符序列abch的所有后綴在Trie樹中最長前綴為ch。）我們比較i節(jié)點和ch中的h的所有子節(jié)點，發(fā)現(xiàn)h只有一個n的子節(jié)點，所以沒辦法匹配，那就繼續(xù)找ch中h的fail指針，圖中沒畫出，那么就是它的fail指針就是root，然后去看root所有子節(jié)點中有沒有和i相等的，發(fā)現(xiàn)最右邊的i是和我們要找的i相等的，所以我們就把i的fail指針指向i，如后面的圖。
五 代碼實現(xiàn)
import java.util.ArrayList;
import java.util.HashMap;
import java.util.LinkedList;
import java.util.List;
import java.util.Map.Entry;
public class AhoCorasickAutomation {
/*本示例中的AC自動機只處理英文類型的字符串，所以數(shù)組的長度是128*/
private static final int ASCII = 128;
/*AC自動機的根結(jié)點，根結(jié)點不存儲任何字符信息*/
private Node root;
/*待查找的目標字符串集合*/
private List<String> target;
/*表示在文本字符串中查找的結(jié)果，key表示目標字符串， value表示目標字符串在文本串出現(xiàn)的位置*/
private HashMap<String, List<Integer>> result;
/*內(nèi)部靜態(tài)類，用于表示AC自動機的每個結(jié)點，在每個結(jié)點中我們并沒有存儲該結(jié)點對應的字符*/
private static class Node{
/*如果該結(jié)點是一個終點，即，從根結(jié)點到此結(jié)點表示了一個目標字符串，則str != null, 且str就表示該字符串*/
String str;
/*ASCII == 128, 所以這里相當于128叉樹*/
Node[] table = new Node[ASCII];
/*當前結(jié)點的孩子結(jié)點不能匹配文本串中的某個字符時，下一個應該查找的結(jié)點*/
Node fail;
public boolean isWord(){
return str != null;
}
}
/*target表示待查找的目標字符串集合*/
public AhoCorasickAutomation(List<String> target){
root = new Node();
this.target = target;
buildTrieTree();
build_AC_FromTrie();
}
/*由目標字符串構(gòu)建Trie樹*/
private void buildTrieTree(){
for(String targetStr : target){
Node curr = root;
for(int i = 0; i < targetStr.length(); i++){
char ch = targetStr.charAt(i);
if(curr.table[ch] == null){
curr.table[ch] = new Node();
}
curr = curr.table[ch];
}
/*將每個目標字符串的最后一個字符對應的結(jié)點變成終點*/
curr.str = targetStr;
}
}
/*由Trie樹構(gòu)建AC自動機，本質(zhì)是一個自動機，相當于構(gòu)建KMP算法的next數(shù)組*/
private void build_AC_FromTrie(){
/*廣度優(yōu)先遍歷所使用的隊列*/
LinkedList<Node> queue = new LinkedList<Node>();
/*單獨處理根結(jié)點的所有孩子結(jié)點*/
for(Node x : root.table){
if(x != null){
/*根結(jié)點的所有孩子結(jié)點的fail都指向根結(jié)點*/
x.fail = root;
queue.addLast(x);/*所有根結(jié)點的孩子結(jié)點入列*/
}
}
while(!queue.isEmpty()){
/*確定出列結(jié)點的所有孩子結(jié)點的fail的指向*/
Node p = queue.removeFirst();
for(int i = 0; i < p.table.length; i++){
if(p.table[i] != null){
/*孩子結(jié)點入列*/
queue.addLast(p.table[i]);
/*從p.fail開始找起*/
Node failTo = p.fail;
while(true){
/*說明找到了根結(jié)點還沒有找到*/
if(failTo == null){
p.table[i].fail = root;
break;
}
/*說明有公共前綴*/
if(failTo.table[i] != null){
p.table[i].fail = failTo.table[i];
break;
}else{/*繼續(xù)向上尋找*/
failTo = failTo.fail;
}
}
}
}
}
}
/*在文本串中查找所有的目標字符串*/
public HashMap<String, List<Integer>> find(String text){
/*創(chuàng)建一個表示存儲結(jié)果的對象*/
result = new HashMap<String, List<Integer>>();
for(String s : target){
result.put(s, new LinkedList<Integer>());
}
Node curr = root;
int i = 0;
while(i < text.length()){
/*文本串中的字符*/
char ch = text.charAt(i);
/*文本串中的字符和AC自動機中的字符進行比較*/
if(curr.table[ch] != null){
/*若相等，自動機進入下一狀態(tài)*/
curr = curr.table[ch];
if(curr.isWord()){
result.get(curr.str).add(i - curr.str.length()+1);
}
/*這里很容易被忽視，因為一個目標串的中間某部分字符串可能正好包含另一個目標字符串，
* 即使當前結(jié)點不表示一個目標字符串的終點，但到當前結(jié)點為止可能恰好包含了一個字符串*/
if(curr.fail != null && curr.fail.isWord()){
result.get(curr.fail.str).add(i - curr.fail.str.length()+1);
}
/*索引自增，指向下一個文本串中的字符*/
i++;
}else{
/*若不等，找到下一個應該比較的狀態(tài)*/
curr = curr.fail;
/*到根結(jié)點還未找到，說明文本串中以ch作為結(jié)束的字符片段不是任何目標字符串的前綴，
* 狀態(tài)機重置，比較下一個字符*/
if(curr == null){
curr = root;
i++;
}
}
}
return result;
}
public static void main(String[] args){
List<String> target = new ArrayList<String>();
target.add("abcdef");
target.add("abhab");
target.add("bcd");
target.add("cde");
target.add("cdfkcdf");
String text = "bcabcdebcedfabcdefababkabhabk";
AhoCorasickAutomation aca = new AhoCorasickAutomation(target);
HashMap<String, List<Integer>> result = aca.find(text);
System.out.println(text);
for(Entry<String, List<Integer>> entry : result.entrySet()){
System.out.println(entry.getKey()+" : " + entry.getValue());
}
}
}
