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

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條評論
主站蜘蛛池模板: 狠狠色噜噜狠狠狠狠狠色综合久久 | 久久精品久久久久 | 欧美精品一区在线看 | 国产91精品高清一区二区三区 | 精品无人区乱码一区二区 | 韩国一级特黄毛片大 | 日韩成人免费aa在线看 | 奇米第四色在线视频 | 99中文字幕 | 成人免费视频日本 | 国产成人综合91精品 | 久久精品国产半推半就 | 在线欧美一区 | 亚洲天堂777| 国产色婷婷免费视频 | 亚洲久热 | 99精品久久 | 奇米影音四色 | 日韩欧美天堂 | 狠狠色噜噜狠狠狠狠2021天天 | 9久9久女女热精品视频免费观看 | 亚洲精品成人久久久影院 | 亚洲综合精品一二三区在线 | 亚洲欧洲国产精品 | 久久久久久久久久爱 | 毛片黄 | aaa大片| 久久国产视频在线观看 | 秘密影院久久综合亚洲综合 | 国产日韩精品一区在线观看播放 | 欧美欧美aaaaa一级毛片 | 快播视频在线 | 色狗综合 | 国产精品视频一区牛牛视频 | 8090色| 黄视频在线观看www 黄视频在线观看网站 | 亚洲人成依人成综合网 | 国产日韩欧美精品在线 | 四虎影视大全 | 尤物福利在线 | 人人爱操 |