多模式串匹配之a(chǎn)c自動機(jī)算法-免費(fèi)閱讀
【正文】 } Build_AC_Automation()。T)。T。}int } {amp。idx = msg[i]39。 } } scanf(%s, s)。idx = s[i]39。 }}*que[MAXQ], *root。 bool danger。const // 前進(jìn) // initial state (root)for i := 1 to m do以上兩種情況直到目標(biāo)字符串指針直到末尾結(jié)束匹配。假定目標(biāo)字符串為ushers，字典為上圖（圖1）所示。樹邊就是單詞中的字符，單詞中最后一個字符的連接節(jié)點(diǎn)添加標(biāo)志，以表示改節(jié)點(diǎn)路徑包含1個字典中的字符串，搜索到此節(jié)點(diǎn)就表示找到了字典中的某個單詞，可以直接輸出?？瓷厦婺莻€圖，想起點(diǎn)兒什么東西沒有？對了，是KMP算法。而且這個狀態(tài)節(jié)點(diǎn)，是所有具備這些條件的節(jié)點(diǎn)中深度最大的那個節(jié)點(diǎn)。轉(zhuǎn)向函數(shù)，指的是一種狀態(tài)之間的轉(zhuǎn)向關(guān)系。AC算法思想：用多模式串建立一個確定性的樹形有限狀態(tài)機(jī)，以主串作為該有限狀態(tài)機(jī)的輸入，使?fàn)顟B(tài)機(jī)進(jìn)行狀態(tài)的轉(zhuǎn)換，當(dāng)?shù)竭_(dá)某些特定的狀態(tài)時，說明發(fā)生模式匹配。該算法在1975年產(chǎn)生于貝爾實驗室，是著名的多模匹配算法之一。學(xué)習(xí)AC自動機(jī)算法之前，最好先熟悉KMP算法，因為KMP算法與字典樹tire的構(gòu)造很是類似。當(dāng)狀態(tài)轉(zhuǎn)移到2，5，7，9等紅色狀態(tài)點(diǎn)時，說明發(fā)生了模式匹配。在構(gòu)造轉(zhuǎn)向函數(shù)時，把不存在的轉(zhuǎn)換用failstate表示，但是failstate不是一個具體的狀態(tài)，狀態(tài)機(jī)轉(zhuǎn)換轉(zhuǎn)換到failstate狀態(tài)的時候就不知道該往哪轉(zhuǎn)了。字符串s相同，并且狀態(tài)3是滿足此條件的唯一節(jié)點(diǎn)，則f(9)=3。例：模式串為：he/ she/ hers/ his 時。四、搜索路徑的確定我的理解是：利用后綴字符串來確定。然后從當(dāng)前回溯節(jié)點(diǎn)判斷是否可以到達(dá)目標(biāo)字符串字符。以上就是我對該算法的全部過程的理解，疏漏之處在所難免。 }end for。int MAXQ = 500000+10。 memset(next, NULL, sizeof(next))。 N。 int TrieNode *ptr = root。voidi。s[100]。 i++) }} int que[0] = root。 i 26。 int TrieNode *ptr = root。 if(ptr == NULL) ptr = root。 { return 0。 scanf(%s, msg)。 tmpt != 1) TrieNode *tmp
環(huán)評公示相關(guān)推薦
鄂ICP備17016276號-1