KMP

KMP算法是一種用於字元串匹配的算法，這個算法的高效之處在於當在某個位置匹配不成功的時候可以根據之前的匹配結果從模式字元串的另一個位置開始，而不必從頭開始匹配字元串。

基本信息

• 中文名：KMP

• 類型：算法
• 方式：分析模式字元串
• 時間：計算每個位置發生不匹配的時候

定義

KMP算法

一種由Knuth(D.E.Knuth)、Morris(J.H.Morris）和Pratt(V.R.Pratt）三人設計的線性時間字元串匹配算法。這個算法不用計算變遷函式δ，匹配時間為Θ（n），只用到輔助函式π[1，m]，它是在Θ（m）時間內，根據模式預先計算出來的。數組π使得我們可以按需要，“現場”有效的計算（在平攤意義上來說）變遷函式δ。粗略地說，對任意狀態q=0，1，…，m和任意字元a∈Σ，π[q]的值包含了與a無關但在計算δ（q，a）時需要的信息。由於數組π只有m個元素，而δ有Θ（m∣Σ∣）個值，所以通過預先計算π而不是δ，使得時間減少了一個Σ因子。
2偽代碼

偽代碼

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25

KMP - MATCHER(T，P) n←length[T] m←length[P] π←COMPUTE - PREFIX - FUNCTION(P) q← 0 / / Numberofcharactersmatched. fori← 1ton / / Scanthetextfromlefttoright. dowhileq> 0andP [q + 1 ]≠T[i] doq←π[q]　 / / Nextcharacterdoesnotmatch. ifP[q + 1 ] = T[i] thenq←q + 1 / / Nextcharactermatches. ifq = m　 / / IsallofPmatched? thenprint "Patternoccurswithshift" i - m q←π[q]　 / / Lookforthenextmatch. COMPUTE - PERFIX - FUNCTION(P) m←length[P] π[ 1 ]← 0 k← 0 forq← 2tom dowhilek> 0andP [k + 1 ]≠P[q] dok←π[k] ifP[k + 1 ] = P[q] thenk←k + 1 π[q]←k return π

Python代碼

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26

defprefix( str ): m = len ( str ) pi = [ 0foriinrange (m)] pi[ 0 ] = 0 k = 0 forqinrange( 1 ,m): whilek> 0andstr [k]! = str [q]: k = pi[k - 1 ] ifstr[k] = = str [q]: k = k + 1 pi[q] = k returnpi defmatch(t,p): n = len (t) m = len (p) pi = prefix(p) q = 0 foriinrange( 0 ,n): whileq> 0andp [q]! = t[i]: q = pi[q - 1 ] ifp[q] = = t[i]: q = q + 1 ifq = = m: print ( "matchedin%d.\n" % (i - m + 1 )) print ( "notmatched!\n" )

詳細闡述

當我們分析一個模式字元串時，例如：abcabcddes.需要分析一下，每個字元x前面最多有多少個連續的字元和字元串從初始位置開始的字元匹配。然後+1就行了（別忘了，我們的字元串都是從索引1開始的）當然，不要相同位置自己匹配，默認第一個字元的匹配數是0。
設字元串為x1,x2,x3...xn，其中x1，x2，x3，...xi，...xn均是字元，設ai為字元xi對應的整數。若且唯若滿足如下條件：字元串x1x2...xmequals字元串x(i-m+1）...xi-1xi並且x1x2...xmx(m+1）unequalsx(i-m)x(i-m+1）...xi-1xi，則a=m。
例如：
abcabcddes
0111234111
|----------------------默認是0
--|||-----------------不能自己在相同位置進行字元匹配，所以這裡認為沒有匹配字元串，所以0+1=1，繼續從1開始匹配
------|||-----------前面的字元和開始位置的字元相同，所以是2,3,4
-----------||||-------不匹配只能取1。
希望能明白的是，如果開始字元是Ch1的話，那么我們就是要在串中第2個Ch1後面的位置開始自己和自己匹配，計算最大的吻合度。
C示例

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50

//c++實現的<a target="_blank" href="/subview/659777/659777.htm">KMP算法</a>，所有涉及字元串，其初始下標從0開始（上述算法均是從1開始） //example:chars[100],t[100];cin>>s>>t;KMP(s,t); //獲取待查詢模式的next數組 int *get_next( char *T, int *next) { inti=0,j=-1; intlength=<a target= "_blank" href= "/subview/736226/5092487.htm" > strlen </a>(T); int *temp=next; *next=-1; <a target= "_blank" href= "/subview/1455003/1455003.htm" > while </a>(i<length) { if (j==-1||*(T+i)==*(T+j)) { i++; j++; //最佳化後的get_next方法，可以防止出現形如"aaaaab"這種模式的計算退化 if (*(T+i)!=*(T+j)) *(next+i)=j; else *(next+i)=*(next+j); } else j=*(next+j); } returntemp; } //<a target="_blank" href="/subview/659777/659777.htm">KMP算法</a> intKMP( char *S, char *T) { intS_Length=<a target= "_blank" href= "/subview/736226/5092487.htm" > strlen </a>(S); intT_Length= strlen (T); //若模式長度大於字元串，則直接返回查詢失敗 if (S_Length<T_Length) return0; inti=0,j=0; int *next=newint[T_Length]; get_next(T,next); <a target= "_blank" href= "/subview/1455003/1455003.htm" > while </a>(i<S_Length&&j<T_Length) { if (j==-1||*(S+i)==*(T+j)) { i++; j++; } else j=*(next+j); } if (j>=T_Length) returni-T_Length; return0; }

在此提供一個更簡明的適用於字元串的kmp實現：

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54

#include<iostream> #include<string.h> intnext[100]; voidgetnext(charb[]) { inti=1,j=0; //i是每個位子，j是回退的位子 next[1]=0; <a target= "_blank" href= "/subview/1455003/1455003.htm" > while </a>(i<=<a target= "_blank" href= "/subview/736226/5092487.htm" > strlen </a>(b)) { if (j==0||b[i-1]==b[j-1]) { i++; j++; next[i]=j; } else j=next[j]; //用上一個的回退關係 } } intkmp(chara[],charb[]) { inti=1,j=1; //i是<a target="_blank" href="/subview/5594190/5635509.htm">主串</a>中的位子，j匹配串的位子 <a target= "_blank" href= "/subview/1455003/1455003.htm" > while </a>(i<=<a target= "_blank" href= "/subview/736226/5092487.htm" > strlen </a>(a)&&j<= strlen (b)) { if (j==0||a[i-1]==b[j-1]) { i++; j++; } else j=next[j]; } if (j> strlen (b)) returni- strlen (b); else return0; } intmain() { chara[40],b[40]; <a target= "_blank" href= "/subview/410546/410546.htm" > printf </a>( "要匹配的<a target=" _blank " href=" /subview/5594190/5635509.htm ">主串</a>：\n" ); <a target= "_blank" href= "/subview/1390039/1390039.htm" > scanf </a>( "%s" ,a); printf ( "要匹配的目標字元串：\n" ); scanf ( "%s" ,b); getnext(b); printf ( "輸出next值：\n" ); for (inti=1;i<=<a target= "_blank" href= "/subview/736226/5092487.htm" > strlen </a>(b);i++) printf ( "%d" ,next[i]); <a target= "_blank" href= "/subview/410546/410546.htm" > printf </a>( "\n" ); printf ( "%d" ,kmp(a,b)); <a target= "_blank" href= "/subview/627587/14965930.htm" > system </a>( "pause" ); main(); return0; }

C示例改進過程根據題設，程式可寫成：

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16

voidGetNext( char *T, int *next) { intk=1,j=0; next[1]=0; while (k<T[0]) { if (j==0||T[k]==T[j]) { ++k; ++j; next[k]=j; } else j=next[j]; } }

但是這個不是最優的，因為他沒有考慮aaaaaaaaaaaaaaaaaaab的情況，這樣前面會出現大量的1，這樣的算法複雜度已經和最初的樸素算法沒有區別了。所以稍微改動一下：

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19

voidGetNextEx( char *T, int *next) { intk=1,j=0; next[1]=0; <a target= "_blank" href= "/subview/1455003/1455003.htm" > while </a>(k<<a target= "_blank" href= "/subview/736226/5092487.htm" > strlen </a>(T)) { if (j==0||T[k]==T[j]) { ++k; ++j; if (T[k]==T[j]) next[k]=next[j]; else next[k]=j; } else j=next[j]; } }

現在我們已經可以得到這個next字元串的值了，接下來就是KMP算法的本體了：
相當簡單：

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19

intKMP( char *S, char *T,intpos) { intk=pos,j=1; inttt=<a target= "_blank" href= "/subview/736226/5092487.htm" > strlen </a>(S); <a target= "_blank" href= "/subview/1455003/1455003.htm" > while </a>(k<tt) { if (S[k]==T[j]) { ++k; ++j; } else j=next[j]; } if (j>T[0]) returnk-T[0]; else return0; }

和樸素算法相比，只是修改一句話而已，但是算法複雜度從O(m*n)變成了：O(m+n)對比

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21

//findatemplateinastring. #include<string.h> #include<stdio.h> intIndex( char *S, char *T,intpos) //pos記錄從哪一位開始匹配可以直接用0代替 { intk=pos,j=0; <a target= "_blank" href= "/subview/1455003/1455003.htm" > while </a>(k<<a target= "_blank" href= "/subview/736226/5092487.htm" > strlen </a>(S)&&j< strlen (T)) //未超出字元串的長度 { if (S[k+j]==T[j]) ++j; //如果相同，則繼續向後比較 else { k++; j=0; } //如果不同，就回溯，重新查找 } if (j== strlen (T)) returnk； else return0; }

實際套用

用KMP算法，計算串的最大匹配論文
摘要
給定兩個串S和T，長分別m和n，本文給出了一個找出二串間最大匹配的算法。該算法可用於比較兩個串S和T的相似程度，它與串的模式匹配有別。
關鍵字
模式匹配串的最大匹配算法
AlgorithmonMaximalMatchingofStrings
LinYuCaiXiangYongHongZhangChunXiaZhangJianJun
（ComputerScienceDepartmentofYunnanNormalUniversityKunming650092）
ABSTRACTGivenTwoStringsSoflengthmandToflengthn，thepaperpresentsanalgorithmwhichfindsthemaximalmatchingofthem.ThealgorithmcanbeusedtocomparethesimilarilityofthetwostringsSandT,itisdifferentwiththestrings'pattrenmatching.
KEYWORDSPatternMatchingMaximalMatchingofStringsAlgorithm
提出問題
字元串的模式匹配主要用於文本處理，例如文本編輯。文本數據的存儲（文本壓縮）和數據檢索系統。所謂字元串的模式匹配[2]，就是給定兩個字元串S和T，長度分別為m和n，找出T中出現的一個或多個或所有的S，在這方面已經取得了不少進展。本文從文本處理的另一個角度出發，找出兩個串的最大匹配，比較其相似程度。它主要套用於文本比較，特別是在計算機輔助教學中。顯然前者要找S的完全匹配，而後者並無此要求。例如，若S=ABCD，T=EFABCDX，那么模式匹配的結果就是找出了T中的一個ABCD，而我們算法的結果就是S能與T的ABCD完全匹配，但是T中還有3個字元是比S多出來的，也就是說在S中有100%的字元與T中的匹配，而在T中有57%的字元與S中的匹配。若S=ABCDFE，T=AFXBECDY。則在模式匹配中S與T無匹配項，但在我們的算法中就能發現T中存在A，B，C，D，但D後不存在E，F。而且S中也存在A，B，C，D，且具有順序性。這樣就能公正地評價S，T的區別。得知其相似程度。
文章的組織如下：首先介紹基本定義和問題的描述；第三節是算法設計；最後是本文總結。
問題描述
設∑為任意有限集，其元稱為字元，w：∑→N為∑到N的函式，稱為∑的權函式（註：本文僅討論權值恆為1的情況）。∑*為∑上的有限字元串集合，那么對任意S，T∈∑*，設S=a1a2…am，T=b1b2…bn，m>0，n>0。記<m>={1,2，…，m},<n>={1,2，…，n}，則稱{(i,j）∣i∈<m>；，j∈<n>；，ai=bj}為S與T的匹配關係集，記作M（S，T），稱M為S與T的一個（容許）匹配，若對任意（i,j），（i',j'）∈，①i<i'，若且唯若j<j'，②i=i'若且唯若j=j'。S與T的匹配中滿足最大者，稱為S與T的最大匹配。若C(i,j）為N上的m×n矩陣，且滿足：
則稱矩陣C為串S與T的匹配關係陣。
於是求串S與T的最大匹配，等價於求C中的一個最大獨立點集M，它滿足，若ci,j，ci',j'∈M，則i<i'若且唯若j<j'，i=i'若且唯若j=j'。我們稱這樣的最大獨立點集為C的最大C-獨立點集。
例：設∑為所有字母的集合，對任意x∈∑，w（x）≡1，設S與T分別為：S=“BOOKNEWS”，T=“NEWBOOKS”。則我們可以得到S與T兩個匹配：
這裡=5；
這裡=4。
顯然為串S與T的最大匹配。
S與T的匹配關係陣C可表示如下：
其中帶圈的部分為一最大C-獨立點集。
設計
我們僅就權值為一的情況進行討論。
設S和T為任意給定串，C為的S與T匹配關係陣，那么由2的討論知，求S與T的最大匹配問題，等價於求C的最大C-獨立點集問題。因而，為了解決我們的問題，只要給出求C的最大C-獨立點集的算法就可以了。
顯然，為了求出C的最大C-獨立點集，我們可以採用這樣的方法：搜尋C的所有C-獨立點集，並找出它的最大者。這種方法是可行的，但並不是非常有效的。這會使問題變得很繁，複雜度很大。因此，我們先對問題進行分析。
在下面的討論中，我們把C的任一C-獨立點集={ai1,j1，…，ais,js}，記作=ai1,j1…ais,js，i1<；…<is。於是可看作陣C中以1為節點的一條路，滿足：對路中的任意兩節點，均有某一節點位於另一節點的右下方。稱這種路為右下行路。
於是求C-獨立點集等價於求陣C的右下行路。這種求右下行路的搜尋可以逐行往下進行。
命題1.若=αai,jβ和ψ=α'ai,jσ為C的兩個C-獨立點集，且α為α'的加細，則存在C-獨立點集'=αai,jδ，滿足≥。
命題2.若=αai,jβ和ψ=α'ai+k,jσ為C的兩個C-獨立點集，且≥，則存在C-獨立點集'=αai,jδ，滿足≥。
命題3.若=αai,jβ和ψ=α'ai,j+kσ為C的兩個C-獨立點集，且≥，則存在C-獨立點集'=αai,jδ，滿足≥。
由命題1知，在搜尋右下行路的過程中，如果已獲得了某一C-獨立點集的某一初始截段αai,j和另一C-獨立點集ψ的某一初始截段α'ai,j，且有≤，則我們可以停止對ψ的進一步搜尋。
由命題2知，在搜尋右下行路的過程中，在某一列j存在某兩個C-獨立點集的某初始截段=ai1,j1…ais,j和ψ=al1,m1…alt,j，如果≥，但lt>is，則我們可以停止對ψ的進一步搜尋。
由命題3知，在搜尋右下行路的過程中，在某一行i存在某兩個C-獨立點集的某初始截段=ai1,j1…ai,js和ψ=ai1,m1…ai,mt，如果≥，但mt>js，則我們可以停止對ψ的進一步搜尋。
由此可見，並不要求搜尋所有C的最大C-獨立點集，而可以採用比這簡單得多的方法進行計算。那么按照我們上面的三個命題，來看如下實例：
首先我們得到=B（在上的節點用①表示），我們向右下方找路，可以發現，在第4列有兩個1，根據命題2，我們選擇上面的一個1，也就是說選擇第1行的那個1，而不要第2行的那個1。同時我們也發現在第1行也有兩個1，由命題3知，我們選擇左邊的那個1，即第4列的那個1。此時=BO。但是當我們的算法運行到第4行時，=BOOK，由於K在第3行第6列，而本行的1在第1列，在路最後一個節點K的左邊，那么我們必須新建一條路ψ，因為我們並不能確定是否以後就有≥，當算法運行到第6行時，=BOOK，ψ=NEW，=4，=3，我們將S鏈到路上，此時我們得到最長右下行路=BOOKS，=5。這樣我們就可以計算出這兩個字元串的匹配程度。
在我們的算法設計過程中，用到了兩個技巧。技巧之一，矩陣C不用存儲，是動態建立的，節省了空間。技巧之二，本算法並不要求所有的S與T中所有的元素都相互進行比較，也並不存儲所有的右下行路，節省了時間和空間。由矩陣中1的出現情況可見，本算法所需的空間和時間都遠小於O（mn）
結束語
本文給出了一個與模式匹配不同的，具有若干套用的，串的最大匹配算法，該算法已經在機器上實現，達到了預期的效果。本文僅討論權值恆為1的情況，對於權值任意的情形不難由此得到推廣。