AC自動機（為什麼講義裡沒有="=）

Aho Corasick Automaton
（還是覺得很煩，為什麼講義裡沒有，害我一直以為不用用這個＝＝）-> tioj 1723

其實他的想法跟KMP是一樣的，徹底了解KMP的人，對AC自動機一定可以很快的有體會。

搞不好，在想這題的時候，就會自然而然的想到這個作法，只是因為一些地方會覺得這個作法不可行，但其實稍做優化，就可以在時限內解決。


＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝即將進入正文＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝


他聽起來很厲害，一年前聽到的時候，覺得他是某種很高尚的東西，但他其實不過就是一個用來做多字串匹配的演算法。（而且他真的很像KMP）


還記得KMP嘛？概念就是做到某個前綴時發現不行，那就找他的某個後綴去試（failure function）AC自動機也是類似的概念。


AC自動機：


1. 先對多字串建出一棵Trie（我這個人不喜歡pointer，所以我都用array實作，開一個[N][26]的陣列。但因為N很大，算一下其實會發現他會MLE，我試了好久，發現只要把它改成一維的，他好像就會把沒有存取過的點視為未使用，但開二維的他卻會因為你把[1][2]存了，而認為你使用了所有[1][0]~[1][25]的所有空間而認定你MLE了，這只是個偷吃布的怪作法，但tioj可以騙到，搞不好連自己的電腦都可以這樣騙?!）


2. 用類似的方法建出failure function（因為你要做的是先求深度淺的再慢慢往較深的地方走，就跟KMP一樣，所以通常會使用BFS）


3. 要多記錄output function（他其實跟failure function很像，但是因為這裡面會有很多個匹配字串，所以當你發現某一個匹配字串被匹配時，你要把它所有也是某個匹配字串的后綴都印出來，或做一些操作，製作方式可以直接拿failure function過來，只要確定他是某個匹配字串即可）


4. 開始匹配！（基本上跟KMP一樣，除了最後找到的時候，要遞迴一下output function）


時間複雜度：

1. O(n)（阿就Trie阿）
2. O(n)（理由與KMP相同）
3. O(n)（理由與2. 相同）
4. O(n)+O(m)+O(K)（這裡比較特別，前兩個跟KMP也是一樣的，O(K)卻是新的東西，他代表著所有的匹配字串總共在文章中幾次，這就是我說的會讓你以為不行的地方，但其實可以用各種方法把這問題去除掉，我是用sort的，但可以不要把所有的output function都做一遍，可以先改那個節點，最後再DP跑過去）

code: http://codepad.org/nh65NWcc