1. 那些經典演算法：AC自動機
第一次看到這個名字的時候覺得非常高級，深入學習就發現，AC就是一種多模式字元串匹配演算法。前面介紹的BF演算法，RK演算法，BM演算法，KMP演算法都屬於單模式匹配演算法，而Trie樹是多模式匹配演算法，多模式匹配演算法就是在一個主串中查找多個模式串，舉個最常用的例子，比如我們在論壇發表評論或發帖的時候，一般論壇後台會檢測我們發的內容是否有敏感詞，如果有敏感詞要麼是用***替換，要麼是不讓你發送，我們評論是通常是一段話，這些敏感詞可能成千上萬，如果用每個敏感詞都在評論的內容中查找，效率會非常低，AC自動機中，主串會與所有的模式串同時匹配，這時候就可以利用AC自動機這種多模式匹配演算法來完成高效的匹配，
AC自動機演算法是構造一個Trie樹，然後再添加額外的失配指針。這些額外的適配指針准許在查找字元串失敗的時候進行回退（例如在Trie樹種查找單詞bef失敗後，但是在Trie樹種存中bea這個單詞，失配指針會指向前綴be），轉向某些前綴分支，免於重復匹配前綴，提高演算法效率。
常見於IDS軟體或病毒檢測軟體中病毒特徵字元串，可以構建AC自動機，在這種情況下，演算法的時間復雜度為輸入字元串的長度和匹配數量之和。
假設現有模式字元串集合：{abd,abdk, abchijn, chnit, ijabdf, ijaij} 構建AC自動機如下：
說明：
1）當前指針curr指向AC自動機的根節點：curr=root。
2）從文本串中讀取（下）一個字元。
3）從當前節點的所有孩子節點中尋找與該字元匹配的節點：
4）若fail == null，則說明沒有任何子串為輸入字元串的前綴，這時設置curr = root，執行步驟2.
若fail != null,則將curr指向 fail節點，指向步驟3。
理解起來比較復雜，找網上的一個例子，假設文本串text = 「abchnijabdfk」。
查找過程如下：
說明如下：
1）按照字元串順序依次遍歷到：a-->b-->c-->h ,這時候發現文本串中下一個節點n和Trie樹中下一個節點i不匹配，且h的fail指針非空，跳轉到Trie樹中ch位置。
注意c-->h的時候判斷h不為結束節點，且c的fail指針也不是結束節點。
2）再接著遍歷n-->i,發現i節點在Trie樹中的下一個節點找不到j，且有fail指針，則繼續遍歷，
遍歷到d的時候要注意，d的下一個匹配節點f是結束字元，所以得到匹配字元串：ijabdf，且d的fail節點也是d，且也是結束字元，所以得到匹配字元串abd，不過不是失敗的匹配，所以curr不跳轉。
先將目標字元串插入到Trie樹種，然後通過廣度有限遍歷為每個節點的所有孩子節點找到正確的fail指針。
具體步驟如下：
1）將根節點的所有孩子節點的fail指針指向根節點，然後將根節點的所有孩子節點依次入隊列。
2）若隊列不為空：
2.1）出列一個字元，將出列的節點記為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 繼續2.2
curr.child[i]入列，再次執行步驟2）。
3）隊列為空結束。
每個結點的fail指向的解決順序是按照廣度有限遍歷的順序完成的，或者說層序遍歷的順序進行，我們根據父結點的fail指針來求當前節點的fail指針。
上圖為例，我們要解決y節點的fail指針問題，已經知道y節點的父節點x1的fail是指向x2的，根據fail指針的定義，我們知道紅色橢圓中的字元串序列肯定相等，而且是最長的公共部分。依據y.fail的含義，如果x2的某個孩子節點和節點y表示的表示的字元相等，y的fail就指向它。
如果x2的孩子節點中不存在節點y表示的字元。由於x2.fail指向x3，根據x2.fail的含義，我們知道綠色框中的字元序列是相同的。顯然如果x3的某個孩子和節點y表示字元相等，則y.fail就指向它。
如果x3的孩子節點不存在節點y表示的字元，我們重復這個步驟，直到xi的fail節點指向null，說明我們達到頂層，只要y.fail= root就可以了。
構造過程就是知道當前節點的最長公共前綴的情況下，去確定孩子節點的最長公共前綴。
下圖中，每個節點都有fail虛線，指向根節點的虛線沒畫出，求圖中c的孩子節點h的fail指向：
原圖中，深藍色的框出來的是已經確定fail指針的，求紅色框中h節點的fail指針。
這時候，我們看下h的父親節點c的fail指針指向，為ch中的c（這表示abc字元串的所有後綴bc和c和Trie樹的所有前綴中最長公共部分為c），且這個c節點的孩子節點中有字元為h的字元，所以圖中紅色框中框出的h節點的fail指針指向 ch字元串中的h。
求紅色框中i的fail指針指向，上圖中，我們可以看到i的父親節點h的指向為ch中的h，（也就是說我們的目標字元串結合中所有前綴和字元序列abch的所有後綴在Trie樹中最長前綴為ch。）我們比較i節點和ch中的h的所有子節點，發現h只有一個n的子節點，所以沒辦法匹配，那就繼續找ch中h的fail指針，圖中沒畫出，那麼就是它的fail指針就是root，然後去看root所有子節點中有沒有和i相等的，發現最右邊的i是和我們要找的i相等的，所以我們就把i的fail指針指向i，如後面的圖。
2. 什麼是「AC」
一般說的「AC」，即交流電的意思。