ac自動(dòng)機(jī)

1、關(guān)鍵字:AC自動(dòng)機(jī)自動(dòng)機(jī)有限狀態(tài)自動(dòng)機(jī)Trie字母樹字符串匹配多串匹配算法Note:閱讀本文需要有KMP算法基礎(chǔ)，如果你不知道什么是KMP，請(qǐng)看這里：blogarticle.aspid=146(Matrix67大牛寫的)AC自動(dòng)機(jī)是用來處理多串匹配問題的，即給你很多串，再給你一篇文章，讓你在文章中找這些串是否出現(xiàn)過，在哪出現(xiàn)。也許你考慮過AC自動(dòng)機(jī)名字的含義，我也有過同樣的想法。你現(xiàn)在已經(jīng)知道KMP了，他之所以叫做KMP，是因?yàn)檫@個(gè)算法

2、是由Knuth、Mris、Pratt三個(gè)提出來的，取了這三個(gè)人的名字的頭一個(gè)字母。那么AC自動(dòng)機(jī)也是同樣的，他是AhoCasick。所以不要再YY地認(rèn)為AC自動(dòng)機(jī)是AC(cept)自動(dòng)機(jī)，雖然他確實(shí)能幫你AC一點(diǎn)題目。。。。扯遠(yuǎn)了。。。要學(xué)會(huì)AC自動(dòng)機(jī)，我們必須知道什么是Trie，即字母樹。如果你會(huì)了，請(qǐng)?zhí)^這一段Trie是由字母組成的。先看張圖：這就是一棵Trie樹。用綠色標(biāo)出的點(diǎn)表示一個(gè)單詞的末尾（為什么這樣表示？看下去就知道了）。

3、樹上一條從root到綠色節(jié)點(diǎn)的路徑上的字母，組成了一個(gè)“單詞”。也許你看了這一段，就知道如何構(gòu)建Trie了，那請(qǐng)?zhí)^以下幾段。那么如何來構(gòu)建一棵Trie呢？就讓我從一棵空樹開始，一步步來構(gòu)建他。好了，現(xiàn)在我們已經(jīng)有一棵Trie了，但這還不夠，我們還要在Trie上引入一個(gè)很強(qiáng)大的東西：失敗指針或者說shift數(shù)組或者說Next函數(shù)…..你愛怎么叫怎么叫吧，反正就是KMP的精華所在，這也是我為什么叫你看KMP的原因。KMP中我們用兩個(gè)指針i

4、和j分別表示，A[ij1..i]與B[1..j]完全相等。也就是說，i是不斷增加的，隨著i的增加j相應(yīng)地變化，且j滿足以A[i]結(jié)尾的長(zhǎng)度為j的字符串正好匹配B串的前j個(gè)字符，當(dāng)A[i1]B[j1]，KMP的策略是調(diào)整j的位置（減小j值）使得A[ij1..i]與B[1..j]保持匹配且新的B[j1]恰好與A[i1]匹配（從而使得i和j能繼續(xù)增加）。Trie樹上的失敗指針與此類似。假設(shè)有一個(gè)節(jié)點(diǎn)k，他的失敗指針指向j。那么kj滿足這個(gè)性質(zhì)