亚洲免费在线-亚洲免费在线播放-亚洲免费在线观看-亚洲免费在线观看视频-亚洲免费在线看-亚洲免费在线视频

KMP算法深度解析

系統 1556 0

摘要:KMP算法是字符串匹配的經典算法,由于其O(m+n)的時間復雜度,至今仍被廣泛應用。大道至簡,KMP算法非常簡潔,然而,其內部卻蘊含著玄妙的理論,以至許多人知其然而不知其所以然。本文旨在解開KMP算法的內部玄妙所在,希望能夠有助于學習與理解。

1、KMP算法
一種改進的字符串匹配算法,由D.E.Knuth與V.R.Pratt和J.H.Morris同時發現,因此稱之為KMP算法。此算法可以在O(n+m)的時間數量級上完成串的模式匹配操作,其基本思想是:每當匹配過程中出現字符串比較不等時,不需回溯指針,而是利用已經得到的“部分匹配”結果將模式向右“滑動”盡可能遠的一段距離,繼續進行比較。

2、基于有限自動機理解算法
KMP 算法看似簡單,其實要完全理解還是有困難的。KMP算法其實可以看成是一個有限自動機,分為 2 部分:第一部分自動機的構造 ( 對應一般的說法就是失效函數,轉移函數, overlap 函數 ) ,第二部分在自動機上搜索過程。舉個例子: 目標串 T = acabaabaabcacaabc; 模式串 P=abaabcac ;根據模式串構造自動機,向前的箭頭表示搜索前進的方向。向后的箭頭表示不匹配的回溯,即失效函數,或者狀態變遷函數。例如:
f(j=1) = 0;
f(j=2) = 0;
f(j=3) = 1;
f(j=4) = 1;
f(j=5) = 2;
f(j=6) = 0;
f(j=7) = 1;

KMP本質上是構造了DFA并進行了模擬,因此很顯然一旦從模版T構造了自動機D,用D去匹配主串S的過程就是線性的。KMP最引人入勝的地方就在于構造D的自匹配過程,它充分利用了D是一個DAG的性質,使得構造過程也是線性的。KMP算法不需要計算變遷函數,只用到輔助數組Next,即模式串自身的特征向量。特征向量可以用模式與其自身進行比較,預先計算出來,它可用于加快字符串匹配算法與有限自動機匹配器的執行速度。

KMP算法深度解析


3、Next特征數組構造
模式串P開頭的任意個字符,把它稱為前綴子串,如p0p1p2…pm-1。在P的第i位置的左邊,取出k個字符,稱為i位置的左子串,即pi-k+1... pi-2 pi-1 pi。求出最長的(最大的k)使得前綴子串與左子串相匹配稱為,在第i位的最長前綴串。第i位的最長前綴串的長度k就是模板串P在位置i上的特征數n[i]特征數組成的向量稱為該模式串的特征向量。
可以證明對于任意的模式串p=p0p1…pm-1,確實存在一個由模式串本身唯一確定的與目標串無關的數組next,計算方法為:
(1) 求p0…pi-1中最大相同的前綴和后綴的長度k;
(2) next[i] = k;

作為特殊情況,當i=0時,令next[i] = -1;顯然,對于任意i(0≤i<m),有next[i] < i;假定已經計算得到next[i], 那么next[i+1] = ? 特征數ni ( -1≤ ni ≤ i )是遞歸定義的,定義如下:
(1) n[0] = -1,對于i > 0的n[i] ,假定已知前一位置的特征數 n[i-1]= k ;
(2) 如果pi = pk ,則n[i] = k+1 ;
(3) 當pi ≠ pk 且k≠0時,則令k = n [k -1] ; 讓(3)循環直到條件不滿足;
(4) 當qi ≠ qk 且k = 0時,則ni = 0;

根據以上分析,可以得到Next特征數組的計算方法,算法代碼如下:

文獻[5]中解釋了以上計算方法存在一定缺陷,存在多比較的情況,可對其進行修正,得到如下算法:


4、算法實現
KMP算法的難點就是有限自動機的構造和特征向量的計算。解決了這兩個問題后,具體匹配算法就很簡單了。

int Index_KMP(SString S,SString T,int pos){
//利用模式串T的next函數求T在主串S中第pos個字符之后的位置的KMP算法。
//其中,T非空,1≤pos≤StrLength(S)。
i=pos; j=1;
while(i <= S[0] && j<= T[0]){
if(j == 0 || S[i] == T[j]) { ++i; ++j; }//繼續比較后繼字符
else j = next[j];//模式串象右移動
}
if(j>T[0]) return i-T[0];//匹配成功
else return 0;
}//Index_KMP


算法相關理論分析與證明,以及算法復雜性分析,若感興趣請參考文獻[3]、[4]、[5],這里不再贅述。

5、參考文獻
[1] http://wansishuang.javaeye.com/blog/402018
[2] http://richardxx.yo2.cn/articles/kmp 和extend-kmp算法.html
[3] KMP算法講義PPT(Hu Junfeng, Peking University)
[4] 算法導論(第32章 字符串匹配)
[5] 數據結構(第4章 串)

KMP算法深度解析


更多文章、技術交流、商務合作、聯系博主

微信掃碼或搜索:z360901061

微信掃一掃加我為好友

QQ號聯系: 360901061

您的支持是博主寫作最大的動力,如果您喜歡我的文章,感覺我的文章對您有幫助,請用微信掃描下面二維碼支持博主2元、5元、10元、20元等您想捐的金額吧,狠狠點擊下面給點支持吧,站長非常感激您!手機微信長按不能支付解決辦法:請將微信支付二維碼保存到相冊,切換到微信,然后點擊微信右上角掃一掃功能,選擇支付二維碼完成支付。

【本文對您有幫助就好】

您的支持是博主寫作最大的動力,如果您喜歡我的文章,感覺我的文章對您有幫助,請用微信掃描上面二維碼支持博主2元、5元、10元、自定義金額等您想捐的金額吧,站長會非常 感謝您的哦!!!

發表我的評論
最新評論 總共0條評論
主站蜘蛛池模板: 97免费在线| 日韩一级大毛片欧美一级 | 99九九99九九九视频精品 | 国产综合色香蕉精品五月婷 | 91亚洲精品国产自在现线 | 性生大片一级毛片免费观看 | 九九热在线观看 | 香蕉碰碰人人a久久动漫精品 | 久久成人免费观看草草影院 | 99视频观看| 久久精品亚洲牛牛影视 | 国产日产欧美精品一区二区三区 | 四小虎免费永久观看 | 亚洲精品美女久久久aaa | 亚洲最黄视频 | 国产精品综合视频 | 久热久 | 欧美日韩中文字幕 | 国产精品96久久久久久久 | 国产中文字幕免费观看 | 91网站国产| 九九九九在线精品免费视频 | 国产一区二区久久精品 | 天天综合在线观看 | 婷婷免费在线 | 成人小视频在线观看 | 国产精品美女流白浆视频 | 亚洲人成一区二区三区 | 久久精品国产精品国产精品污 | 99久女女精品视频在线观看 | 5151四虎永久在线精品免费 | 亚洲欧美国产18 | 午夜999| 操熟美女又肥又嫩的骚屁股 | 亚洲你懂的 | 欧美日韩在线网站 | 野外一级毛片黑人 | 奇米影视777狠狠狠888不卡 | 尤物视频在线 | 欧美日韩亚洲视频 | 欧美成人三级视频 |