AC自動機·Aho-Corasick_automation
前置技能（宣傳一下自己的Blog）
KMP字符串匹配（http://www.yaoyaojy.tk/index.php/archives/37/）TRIE字典樹（http://www.yaoyaojy.tk/index.php/archives/38/）
簡介
看dalao們AC自動機的Blog，大多數奆奆都會感性地說：AC_automation = KMP+TRIE然而在作者重蹈覆轍輾轉反側n次後才明白，這東西說了等於沒說。AC自動機是一種有限狀態自動機（說了等於沒說），它常被用於多模式串的字符串匹配。在學完AC自動機，筆者也總結出一句說了等於沒說的話：AC自動機是以TRIE的結構為基礎，結合KMP的思想建立的。
建立AC自動機
建立一個AC自動機通常需要兩個步驟：
基礎的TRIE結構：將所有的模式串構成一棵Trie。KMP的思想：對Trie樹上所有的結點構造失配指針。
然後就可以利用它進行多模式匹配了。
TRIE構建
和trie的insert操作一模一樣（強調！一模一樣！）因為我們只利用TRIE的結構，所以只需將模式串存入即可。
構造失配（fail）指針
在講構造以前，先來對比一下這裡的fail指針與KMP中的next指針：
共同點-兩者同樣是在失配的時候用於跳轉的指針。不同點-KMP要求的是最長相同真前後綴，而AC自動機只需要相同後綴即可。因為KMP只對一個模式串做匹配，而AC自動機要對多個模式串做匹配。有可能fail指針指向的結點對應著另一個模式串，兩者前綴不同。也就是說，AC自動機在對匹配串做逐位匹配時，同一位上可能匹配多個模式串。因此fail指針會在字典樹上的結點來回穿梭，而不像KMP在線性結構上跳轉。
下面介紹構建fail指針的基礎思想：（強調！基礎思想！基礎！）
構建fail指針，可以參考KMP中構造next數組的思想。我們利用部分已經求出fail指針的結點推導出當前結點的fail指針。具體我們用BFS實現：如果結點fail[p]通過字母c連接到的子結點w存在：如果fail[p]通過字母c連接到的子結點w不存在：則讓u的fail指針指向這個結點w（fail[u]=w）。相當於在p和fail[p]後面加一個字符c，就構成了fail[u]。那麼我們繼續找到fail[fail[p]]指針指向的結點，重複上述判斷過程，一直跳fail指針直到根節點。如果真的沒有，就令fail[u]=根節點。考慮字典樹中當前的節點u，u的父節點是p，p通過字符c的邊指向u。假設深度小於u的所有節點的fail指針都已求得。那麼p的fail指針顯然也已求得。我們跳轉到p的fail指針指向的結點fail[p]；如此即完成了fail指針的構建。
下面放一張GIF幫助大家理解：對字典樹{i,he,his,she,hers}構建fail指針：
黃色結點表示當前的結點u，綠色結點表示已經BFS遍歷完畢的結點，紅/橙色的邊表示fail指針。
AC_automation_gif_b_3.gif我們重點分析結點6的fail指針構建：
AC_automation_6_9.png找到6的父節點5，5的fail指針指向10，然而10結點沒有字母's'連出的邊；所以跳到10的fail指針指向的結點0，發現0結點有字母's'連出的邊，指向7結點；所以fail6=7.
另外，在構建fail指針的同時，我們也對TRIE中模式串的結尾構建fail指針。這樣在匹配到結尾後能自動跳轉到下一個匹配項。具體見代碼實現。
從代碼深入剖析
代碼總框架
字典樹or字典圖
關於insert()筆者不做分析，先來看build():
這裡的字典樹根節點為0，我們將根節點的子節點一一入隊。
Q1-等等，為什麼不將根節點入隊，非要將它的子節點入隊？
然後開始BFS：
如果字符i對應的子節點存在，我們就將這個子節點的fail指針賦值為`fail[k]`的字符i對應的結點。
Q2-不是應該用while循環，不停的跳fail指針，判斷是否存在字符i對應的結點，然後賦值嗎？怎麼一句話就完了？
否則，k結點沒有字符i對應的子節點，就將fail[k]的字符i對應的子節點編號賦值給k
Q3-等等，說好的字典樹呢？怎麼將fail[k]的子節點直接賦成k的子節點去了？
每次取出隊首的結點k。注意，結點k本身的fail指針已經求得，我們要求的是k的子節點們的fail指針。
然後遍歷字符集（這裡是0-25，對應a-z）：
這三個Questions構成了fail指針構建的精髓。
Answer to Q1
若將根節點入隊，則在第一次BFS的時候，會將根節點的子節點的fail指針標記為本身。
而將根節點的子節點入隊，也不影響算法正確性（因為fail指針初始化為0）
Answer to Q2&Q3
Q2與Q3的代碼是相輔相成的。
簡單地來講，我們將fail指針跳轉的路徑做了壓縮（就像併查集的路徑壓縮），使得本來需要跳很多次fail指針變成跳一次。
而這個路徑壓縮的就是Q3的代碼在做的事情之一。
我們將之前的GIF圖改一下：
藍色結點表示BFS遍歷到的結點k，深藍色、黑色的邊表示執行完Q3代碼連出的字典樹的邊。
可以發現，眾多交錯的黑色邊將字典樹變成了字典圖。
圖中省略了連向根節點的黑邊（否則會更亂）。
我們重點分析一下結點5遍歷時的情況：
顯然，本來應該跳2次才能找到7號結點，但是我們通過10號結點的黑色邊直接通過字母s找到了7號結點。
因此，Q2結合了Q3的代碼，就能在O(1)的時間內對單個結點構造fail指針。
這就是build完成的兩件事：構建fail指針和建立字典圖。這個字典圖也會在查詢的時候起到關鍵作用。
多模式匹配的真諦
接下來分析匹配函數query():
循環遍歷匹配串，p在字典樹上跟蹤當前字符。
利用fail指針找出所有匹配的模式串，累加到答案中。然後清0。
對e[j]取反的操作用來判斷e[j]是否等於-1。
Q-讀者可能納悶了：你這裡的p一直在往字典樹後面走，沒有跳fail指針啊！這和KMP的思想不一樣啊，怎麼匹配得出來啊
Answer to Q
還記得剛才的字典圖嗎？事實上你並不是一直在往後跳，而是在圖上穿梭跳動。比如，剛才的字典圖：
我們從根節點開始嘗試匹配ushersheishis，那麼p的變化將是：
紅色結點表示p結點，粉色箭頭表示p在字典圖上的跳轉，淺藍色的邊表示成功匹配的模式串，深藍色的結點表示跳fail指針時的結點。
其中的部分跳轉，我們利用的就是新構建的字典圖上的邊，它也滿足後綴相同（sher和her），所以自動跳轉到下一個位置。
綜上，fail指針的意義是，在匹配串同一個位置失配時的跳轉指針，這樣就利用fail指針在同一位置上進行多模式匹配，匹配完了，就在字典圖上自動跳轉到下一位置。
總結-這就是AC自動機
到此，你已經理解了整個AC自動機的內容。我們一句話總結AC自動機的運行原理：構建字典圖實現自動跳轉，構建失配指針實現多模式匹配。你曾經憧憬的，「能自動AC算法題目」的AC自動機，已經掌握了。
完整代碼
洛谷AC自動機模板題簡單版（https://www.luogu.org/problemnew/show/P3808）
練習
洛谷模板題x2
完結撒花
本文發布於洛穀日報，特約作者：水手hwy
原文地址：https://www.luogu.org/blog/42196/qiang-shi-tu-xie-ac-zi-dong-ji