多模式串匹配之a(chǎn)c自動(dòng)機(jī)算法-全文預(yù)覽
【正文】 ot。 int }} i++)s[100]。i。void ptr = ptrnext[idx]。a39。 TrieNode *ptr = root。 int N。//文本字符串char t = 0。 memset(next, NULL, sizeof(next))。 int TrieNode* next[MAXK]。int MAXK = 26。int MAXQ = 500000+10。附3：一個(gè)簡(jiǎn)單的AC算法實(shí)現(xiàn)源碼示例參考： }end for。以上就是我對(duì)該算法的全部過(guò)程的理解，疏漏之處在所難免。在匹配過(guò)程中遇到有標(biāo)志的節(jié)點(diǎn)說(shuō)明找到了字典中的某個(gè)詞，可以直接輸出。然后從當(dāng)前回溯節(jié)點(diǎn)判斷是否可以到達(dá)目標(biāo)字符串字符。搜索過(guò)程目標(biāo)字符串指針指向的字符和字典中的字符會(huì)有以下幾種情況：a. 當(dāng)前字符匹配。四、搜索路徑的確定我的理解是：利用后綴字符串來(lái)確定。Trie是一個(gè)樹(shù)形結(jié)構(gòu)的狀態(tài)裝換圖，從一個(gè)結(jié)點(diǎn)到它的各個(gè)子結(jié)點(diǎn)的邊上有不同的標(biāo)號(hào)。例：模式串為：he/ she/ hers/ his 時(shí)。有人說(shuō)AC算法就是KMP算法在多模式匹配情況下的擴(kuò)展。字符串s相同，并且狀態(tài)3是滿足此條件的唯一節(jié)點(diǎn)，則f(9)=3。如果不存在滿足條件的狀態(tài)節(jié)點(diǎn)，則失效函數(shù)為0。在構(gòu)造轉(zhuǎn)向函數(shù)時(shí)，把不存在的轉(zhuǎn)換用failstate表示，但是failstate不是一個(gè)具體的狀態(tài)，狀態(tài)機(jī)轉(zhuǎn)換轉(zhuǎn)換到failstate狀態(tài)的時(shí)候就不知道該往哪轉(zhuǎn)了。g(pre, x)=next：狀態(tài)pre在輸入一個(gè)字符x后轉(zhuǎn)換為狀態(tài)next（上圖中的實(shí)線部分）。當(dāng)狀態(tài)轉(zhuǎn)移到2，5，7，9等紅色狀態(tài)點(diǎn)時(shí)，說(shuō)明發(fā)生了模式匹配。下圖是多模式he/ she/ his /hers構(gòu)成的一個(gè)確定性有限狀態(tài)機(jī)，做幾點(diǎn)說(shuō)明： 該狀態(tài)機(jī)優(yōu)先按照實(shí)線標(biāo)注的狀態(tài)轉(zhuǎn)換路徑進(jìn)行轉(zhuǎn)換，當(dāng)所有實(shí)線標(biāo)注的狀態(tài)轉(zhuǎn)換路徑條件不能滿足時(shí)，按照虛線的狀態(tài)轉(zhuǎn)換路徑進(jìn)行狀態(tài)轉(zhuǎn)換。學(xué)習(xí)AC自動(dòng)機(jī)算法之前，最好先熟悉KMP算法，因?yàn)镵MP算法與字典樹(shù)tire的構(gòu)造很是類似。AC算法用于在一段文本中查找多個(gè)模式字符串，即給你很多字符串，再給你一段文本，讓你在文本中找這些串是否出現(xiàn)過(guò)，出現(xiàn)過(guò)多少次，分別在哪里出現(xiàn)。 任俠 發(fā)布于 20110322該算法在1975年產(chǎn)生于貝爾實(shí)驗(yàn)室，是著名的多模匹配算法之一。AC算法有三個(gè)主要步驟，一個(gè)是字典樹(shù)tire的構(gòu)造，一個(gè)是搜索路徑的確定（即構(gòu)造失敗指針），還有就是模式匹配過(guò)程。AC算法思想：用多模式串建立一個(gè)確定性的樹(shù)形有限狀態(tài)機(jī)，以主串作為該有限狀態(tài)機(jī)的輸入
環(huán)評(píng)公示相關(guān)推薦
鄂ICP備17016276號(hào)-1