多模式串匹配之a(chǎn)c自動機(jī)算法-預(yù)覽頁
【正文】 ，使?fàn)顟B(tài)機(jī)進(jìn)行狀態(tài)的轉(zhuǎn)換，當(dāng)?shù)竭_(dá)某些特定的狀態(tài)時，說明發(fā)生模式匹配。如主串為：ushers，狀態(tài)轉(zhuǎn)換的過程是這樣的：轉(zhuǎn)向函數(shù)，指的是一種狀態(tài)之間的轉(zhuǎn)向關(guān)系。f(per)=next：是在比較失配的情況下使用的轉(zhuǎn)換關(guān)系。而且這個狀態(tài)節(jié)點(diǎn)，是所有具備這些條件的節(jié)點(diǎn)中深度最大的那個節(jié)點(diǎn)。狀態(tài)3向上到狀態(tài)0經(jīng)過的輸入字符串為s；而由狀態(tài)9向上的輸入字符串為sreh。看上面那個圖，想起點(diǎn)兒什么東西沒有？對了，是KMP算法。樹邊就是單詞中的字符，單詞中最后一個字符的連接節(jié)點(diǎn)添加標(biāo)志，以表示改節(jié)點(diǎn)路徑包含1個字典中的字符串，搜索到此節(jié)點(diǎn)就表示找到了字典中的某個單詞，可以直接輸出。例子：某字典P=｛he,she,his,hers｝對應(yīng)的字典樹如下圖：圖中有數(shù)字的節(jié)點(diǎn)到根節(jié)點(diǎn)的路勁正好對應(yīng)字典中的字符串，數(shù)字表述單詞在字典中的順序，也可以是其他標(biāo)志。假定目標(biāo)字符串為ushers，字典為上圖（圖1）所示。表示當(dāng)前節(jié)點(diǎn)的任何一條邊都無法達(dá)到要匹配的字符，此時不能沿現(xiàn)有路徑前進(jìn)，只能回溯，回溯到存在的最長的后綴字符串處，如果沒有任何后綴字符串匹配則回溯到樹根處。以上兩種情況直到目標(biāo)字符串指針直到末尾結(jié)束匹配。由于固定字典的字符串的后綴字符串都是已知的，因此可以在字典樹結(jié)構(gòu)中存儲匹配失敗的路徑方向，因此只要字典樹構(gòu)造完畢，就可以根據(jù)字典樹的路徑進(jìn)行匹配了，效率非?？?。 // initial state (root)for i := 1 to m do // 前進(jìn)constconstTrieNode{ bool danger。 TrieNode() }}*que[MAXQ], *root。 while(s[i])idx = s[i]39。 ptrdanger = true。} int char root = new TrieNode()。N)。 i N。 scanf(%s, s)。 rootfail = NULL。 for(i = 0。 TrieNode *ptr = curfail。 if(ptrnext[i]danger == true) break。 if(ptr == NULL) curnext[i]fail = root。 } } while(msg[i])idx = msg[i]39。amp。 { ans += tmpt。 } }}intT。T)。 Build_AC_Automation()。 }}
環(huán)評公示相關(guān)推薦
鄂ICP備17016276號-1