kmp算法報(bào)告word版(編輯修改稿)
2024-09-10 21:27 本頁面
【文章內(nèi)容簡(jiǎn)介】 amp。x≠Pj(1≤jm)mj, amp。 其他情況其中j=Max{k|Pk=x,1≤km}Dist(x)函數(shù)的計(jì)算代碼如下：void bmDist(char P[], int m, int Dist[]){ char ch 。 int k 。 for(ch=’a’。ch=’z’。ch++) Dist[ch96]=m 。 // a的ASCII碼值為61H for(k=1。k=m1。k++) Dist[P[k]96]=mk 。 return 。}BM匹配算法的代碼如下：void bmSM(char P[],char T[],int m,int n,int Dist[]){ int i, j, k 。 i = m 。 while(inm+1){ j=m 。 k=i 。 while((j0)amp。amp。(P[j]==T[k])){ j 。 k 。 } if(j==0){ coutkendl 。 return 。 } else i=i+Dist[T[i]96] 。 } cout”Failure”endl 。 return 。} BM算法時(shí)間復(fù)雜度Dist(x)函數(shù)的計(jì)算與兩個(gè)參數(shù)有關(guān)：字符表Σ的大小c和樣本Pattern長(zhǎng)度m，因此Dist(x)函數(shù)的時(shí)間代價(jià)是θ(m+c)階的。BM算法的比較次數(shù)不會(huì)超過m.(nm+1)，因此BM算法的最壞情形時(shí)間復(fù)雜度為θ()。BM算法比起KMP算法有明顯的優(yōu)勢(shì)，KMP算法每次比較后樣本Pattern右移的距離不可能大于該次匹配字符比較的次數(shù)，因此KMP算法在最好情形下，其不成功搜索或搜索所有匹配的比較次數(shù)至少為nm+1。而BM算法中樣本Pattern右移的距離與字符比較數(shù)無關(guān)，多數(shù)情況下每次匹配只需比較一次便可以右移m位，從而使得字符比較總數(shù)大大小于文本Text長(zhǎng)度n。 QuickSearch (QS)算法該算法是對(duì)在BM算法的基礎(chǔ)上的一點(diǎn)改進(jìn)，其核心思想是：發(fā)生不匹配時(shí)(Tji≠Pmi)，至少要向前移動(dòng)一個(gè)字符，也就是說Tj+1一定會(huì)參與下一次匹配，可以利用該字符在Pattern中的出現(xiàn)情況決定本次移動(dòng)的距離。由于該算法并不利用已匹配部分所帶來的goodsuffix shift和badcharacter shift，只是根據(jù)Tj+1所得到的跳越情況進(jìn)行移動(dòng)，所以在理想情況下，會(huì)比BM算法的最大跳越距離多一個(gè)字符(因?yàn)閷j+1本身計(jì)算在內(nèi)了)，所以最優(yōu)情況下復(fù)雜度可以是O(nm+1)，該算法能夠取得較高效率的前提是Text中絕大多數(shù)的字符都是Pattern中沒有的字符，對(duì)應(yīng)實(shí)際的情況就是字符集較大，Patt
教學(xué)課件相關(guān)推薦
鄂ICP備17016276號(hào)-1