kmp演算法英文詳解

㈠ KMP是什麼意思

kmp演算法是一種改進的字元串匹配演算法，由D.E.Knuth與V.R.Pratt和J.H.Morris同時發現，因此人們稱它為克努特——莫里斯——普拉特操作（簡稱KMP演算法）。KMP演算法的關鍵是根據給定的模式串W1,m,定義一個next函數。next函數包含了模式串本身局部匹配的信息。
完全掌握KMP演算法思想
學過數據結構的人，都對KMP演算法印象頗深。

㈡ 求kmp演算法的詳細解釋。（最好附上能運行的程序）

t;i),那麼next[i]就是所有這樣的j的最大值
形象地說,就是假如第i+1個字元匹配失敗之後,下一個可能匹配位置至少應該往後挪動多少

就"abaabc"而言
next[1]=0
next[2]=0
next[3]=1
next[4]=1
next[5]=2
next[6]=0

計算過程基本上抄自演算法導論,假設str長度為n
k=0;//k表示當前匹配了多少位
next[1]=0;
for (i=1;i<n;i++)
{
while (k && str[i]!=str[k]) k=next[k];
if (str[i]==str[k]) k++;
next[i+1]=k;
}

之後計算str和某個長度為m的字元串text匹配的過程基本上是一樣的
k=0;//用於記錄str最長能夠有前k位是text的前i+1個字元的後綴
for (i=0;i<m;i++)
{
while (k && text[i]!=str[k]) k=next[k];//發現不能匹配的時候就把str往後挪
if (text[i]==str[k]) k++;
if (k==n) printf("在位置%d處找到一個匹配\n",i+1-n);
}

對照著後面這一段很容易理解第一段

㈢ KMP模式匹配演算法是什麼

KMP模式匹配演算法是一種改進演算法，是由D.E.Knuth、J.H.Morris和v.R.Pratt提出來的，因此人們稱它為「克努特－莫里斯－普拉特操作」，簡稱KMP演算法。此演算法可以在O（n＋m）的時間數量級上完成串的模式匹配操作。其改進在於：每當一趟匹配過程出現字元不相等時，主串指針i不用回溯，而是利用已經得到的「部分匹配」結果，將模式串的指針j向右「滑動」盡可能遠的一段距離後，繼續進行比較。

1.KMP模式匹配演算法分析回顧圖4－5所示的匹配過程示例，在第三趟匹配中，當i＝7、j＝5字元比較不等時，又從i＝4、j＝1重新開始比較。然而，經仔細觀察發現，i＝4和j＝1、i＝5和j＝1以及i＝6和j＝1這三次比較都是不必進行的。因為從第三趟部分匹配的結果就可得出，主串中的第4、5和6個字元必然是b、c和a（即模式串第2、第2和第4個字元）。因為模式中的第一個字元是a，因此它無須再和這三個字元進行比較，而僅需將模式向右滑動2個字元的位置進行i＝7、j＝2時的字元比較即可。同理，在第一趟匹配中出現字元不等時，僅需將模式串向右移動兩個字元的位置繼續進行i＝2、j＝1時的字元比較。由此，在整個匹配過程中，i指針沒有回溯，如圖1所示。

圖1改進演算法的模式匹配過程示意

㈣ kmp 演算法原理

樸素演算法
先看看最「樸素」的演算法： ///find a template in a string. #include<string.h> #include<stdio.h> int Index(char *S, char *T, int pos) { int k=pos, j=0; while(k <strlen(S) && j<strlen(T))//未超出字元串的長度 { if (S[k] == T[j]) { ++k; ++j;} //如果相同，則繼續向後比較 else {k = k-j+1; j =0;} //如果不同，就回溯，重新查找 } if (j == strlen(T)) return k-strlen（T）; else return 0; }
編輯本段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∣Σ∣)個值，所以通過預先計算π而不是δ，使得時間減少了一個Σ因子。[1] KMP演算法是通過分析子串，預先計算每個位置發生不匹配的時候，所需GOTO的下一個比較位置，整理出來一個next數組，然後在上面的演算法中使用。
編輯本段KMP演算法的講解
當我們分析一個子串時，例如：abcabcddes. 需要分析一下，每個字元x前面最多有多少個連續的字元和字元串從初始位置開始的字元匹配。然後+1就行了（別忘了，我們的字元串都是從索引1開始的）當然，不要相同位置自己匹配，默認第一個字元的匹配數是0。
編輯本段定義
設字元串為 x1x2x3...xn ,其中x1，x2，x3，... xi，... xn均是字元，設ai為字元xi對應的整數。則a=m，當且僅當滿足如下條件：字元串x1x2...xm equals 字元串x(i-m+1)...xi-1 xi 並且x1x2...xm x(m+1) unequals x(i-m) x(i-m+1)...xi-1 xi。
編輯本段舉例
abcabcddes 0111234111 |----------------------默認是0 --| | |-----------------不能自己在相同位置進行字元匹配，所以這里認為沒有匹配字元串，所以0+1 =1，繼續從1開始匹配 ------| | |-----------前面的字元和開始位置的字元相同，所以是2,3,4 -----------| | | |-------不匹配只能取1。 希望能明白的是，如果開始字元是 Ch1的話，那麼我們就是要在串中第2個Ch1後面的位置開始自己和自己匹配，計算最大的吻合度。 程序寫出來就是： void GetNext(char* T, int *next) { int k=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，這樣的演算法復雜度已經和最初的樸素演算法沒有區別了。所以稍微改動一下： void GetNextEx(char *T, char *next) { int k=1,j=0; next[1] = 0; while(k < T[0]) { 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演算法的本體了： 相當簡單： int KMP(char* S, char* T, int pos) { int k=pos, j=1; while (k){ if (S[k] == T[j]){ ++k; ++j; } else j = next[j]; } if (j>T[0]) return k-T[0]; else return 0; } 和樸素演算法相比，只是修改一句話而已，但是演算法復雜度從O(m*n) 變成了：O(m)
編輯本段KMP演算法的偽代碼
KMP-MATCHER(T，P) 1n ← length[T] 2m ←length[P] 3π ← COMPUTE-PREFIX-FUNCTION(P) 4q ← 0△Number of characters matched. 5for i ← 1 to n△Scan the text from left to right. 6do while q>0 and P[q+1]≠T[i] 7do q ← π[q]△Next character does not match. 8if P[q+1]=T[i] 9then q ← q+1△Next character matches. 10if q=m△Is all of P matched? 11then print 「Pattern occurs with shift」 i-m 12q ← π[q]△Look for the next match. COMPUTE-PERFIX-FUNCTION(P) 1m ← length[P] 2π[1] ← 0 3k ← 0 4for q ← 2 to m 5do while k>0 and P[k+1]≠P[q] 6do k ← π[k] 7if P[k+1]=P[q] 8then k ← k+1 9π[q] ← k 10return π[1]
編輯本段KMP演算法的c++實現
//c++實現的KMP演算法，所有涉及字元串，其初始下標從0開始(上述演算法均是從1開始) //example: char s[100],t[100];cin>>s>>t;KMP(s,t); //獲取待查詢模式的next數組 int* get_next(char* T, int* next){ int i = 0, j = -1; int length = strlen(T); int *temp = next; *next = -1; while(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); } return temp; } //KMP演算法 int KMP(char *S, char *T){ int S_Length = strlen(S); int T_Length = strlen(T); //若模式長度大於字元串，則直接返回查詢失敗 if( S_Length < T_Length) return 0; int i = 0, j = 0; int* next = new int[T_Length]; get_next(T, next); while(i < S_Length && j < T_Length){ if(j == -1 || *(S+i) == *(T+j)){ i++; j++; } else j=*(next+j); } if(j>=T_Length) return i-T_Length; return 0; } 在此提供一個更簡明的適用於字元串的kmp實現： #include<iostream> #include<string.h> int next[100]; void getnext(char b[]) { int i=1,j=0; //i是每個位子，j是回退的位子 next[1]=0; while(i<=strlen(b)) { if(j==0||b[i-1]==b[j-1]) { i++; j++; next[i]=j; } else j=next[j]; //用上一個的 回退關系 } } int kmp(char a[],char b[]) { int i=1,j=1; //i是主串中的位子 ，j匹配串的位子 while(i<=strlen(a)&&j<=strlen(b)) { if(j==0||a[i-1]==b[j-1]) { i++; j++; } else j=next[j]; } if(j>strlen(b)) return i-strlen(b); else return 0; } int main() { char a[40],b[40]; printf("要匹配的主串：\n"); scanf("%s",a); printf("要匹配的子串：\n"); scanf("%s",b); getnext(b); printf("輸出next值：\n"); for(int i=1;i<=strlen(b);i++) printf("%d ",next[i]); printf("\n"); printf("%d",kmp(a,b)); system("pause"); main(); return 0; }
編輯本段串的最大匹配演算法
摘要：
給定兩個串S和T，長分別m和n，本文給出了一個找出二串間最大匹配的演算法。該演算法可用於比較兩個串S和T的相似程度，它與串的模式匹配有別。
關鍵詞：
模式匹配 串的最大匹配 演算法 Algorithm on Maximal Matching of Strings Lin YuCai Xiang YongHong Zhang ChunXia Zhang JianJun （Computer Science Department of Yunnan Normal University Kunming 650092） ABSTRACT Given Two Strings S of length m and T of length n，the paper presents an algorithm which finds the maximal matching of them. The algorithm can be used to compare the similarility of the two strings S and T, it is different with the strings' pattren matching. KEY WORDS Pattern Matching Maximal Matching of Strings Algorithm
編輯本段問題的提出
字元串的模式匹配主要用於文本處理，例如文本編輯。文本數據的存儲（文本壓縮）和數據檢索系統。所謂字元串的模式匹配[2]，就是給定兩個字元串S和T，長度分別為m和n，找出T中出現的一個或多個或所有的S，在這方面已經取得了不少進展[3][4][5][6][7][8][9][10][11]。本文從文本處理的另一個角度出發，找出兩個串的最大匹配，比較其相似程度[1]。它主要應用於文本比較，特別是在計算機輔助教學中。顯然前者要找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的情況，對於權值任意的情形不難由此得到推廣。
編輯本段C語言代碼(C Code)
#include<stdio.h> #include<string.h> void getnext(int next[],char s[],int l) { int i=1,j=0; next[1]=0; while(i<l) { if(j==0 || s[i]==s[j]) { i++;j++; next[i]=j; } else j=next[j]; } } int KMP(char s1[],char s2[],int l1,int l2,int next[]) { int i,j; i=j=1; while(i<=l1 && j<=l2) { if(j==0||s1[i]==s2[j]) { i++;j++; } else j=next[j]; } if(j>l2) return(i-l2); return 0; } int main() { int next[10001],ans; char s1[10001],s2[10001],l1,l2; scanf("%s",s1+1); scanf("%s",s2+1); l1=strlen(s1+1); l2=strlen(s2+1); getnext(next,s2,l2); ans=KMP(s1,s2,l1,l2,next); if(ans!=0) printf("%d\n",ans); else printf("No!\n"); system("pause"); return 0; }
編輯本段KMP演算法的pascal實現
var next:array [1 ..1000001] of longint; s,t:ansistring; procere get_next(t:ansistring); var j,k:integer; begin j:=1; k:=0; while j<length(t) do begin if (k=0) or (t[j]=t[k]) then begin inc(j); inc(k); next[j]:=k; end else k:=next[k]; end; end; function index(s:ansistring;t:ansistring):longint; var i,j:longint; begin get_next(t); index:=0; i:=1; j:=1; while (i<=length(s))and(j<=length(t)) do begin if (j=0)or(s[i]=t[j]) then begin inc(i); inc(j); end else j:=next[j]; if j>length(t) then index:=i-length(t); end; end; begin readln(s); readln(t); writeln(index(s,t)) end.
編輯本段KMP播放器
K-multimedia player的縮寫
來自韓國的影音全能播放器，與Mplayer一樣從linux平台移植而來的Kmplayer(簡稱KMP)幾乎可以播放您系統上所有的影音文件。通過各種插件擴展KMP可以支持層出不窮的新格式。強大的插件功能,直接從Winamp繼承的插件功能，能夠直接使用winamp的音頻 ，輸入，視覺效果插件，而通過獨有的擴展能力，只要你喜歡，可以選擇使用不同解碼器對各種格式進行解碼。 KMPlayer The Professional Media Player! 它支持 Winamp 2/5 的輸入、常規、DSP、視覺效果、媒體庫插件。無須注冊表支持直接調用 Directshow 濾鏡！FFdshow 的視覺特效系統~超強的 GUI 界面~安裝電視卡後可以直接代替原軟體直接收看電視~支持播放 DVD/VCD 以及絕大多數電腦的媒體文件（AVI 支持 Xvid/DivX/3vid/H264 OGG/OGM/MKV 容器/AC3/DTS 解碼~Monkey Audio 解碼~）強烈推薦！此播放器除了會將自己的配置信息寫入注冊表外絕對綠色~ KMplayer內置目前常見的所有解碼器，包括real,QT等。 另外KMplayer安裝版也是目前很少見的檢查流氓軟體的安裝方式，如果一旦有惡意的漢化小組漢化並捆綁了流氓軟體。該安裝程序自動會識別，並作出提示，建議用戶不要安裝，雖然不是特別准確，但KMplayer的無廣告及第三方插件的特點使其深受好評。 目前韓國官方已經在Kmplayer里自帶了中文字型檔，只要用戶是中文系統，軟體就會自動識別，十分方便。 KMP版本: KMPlayer3.0.0.1439

㈤ 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∣Σ∣）個值，所以通過預先計算π而不是δ，使得時間減少了一個Σ因子。

㈥ 演算法-KMP

大一下參加學校ACM預備隊集訓的時候首次接觸KMP演算法，當時看了很多介紹文章，仍然不是很理解其實質，只是簡單地套模板AC題目，待大二數據結構與演算法課堂上再聽老師介紹一次，才恍然大悟其實KMP也就是那麼回事嘛。但當初為啥看那麼多文章都沒弄明白呢？正巧最近和朋友聊天時他告訴我他對KMP不是很理解，於是打算自己寫一篇文章，鞏固自己對KMP的認識，也希望能夠幫助更多朋友理解KMP。
在開始之前，需要知曉的概念：

前綴：以原串串頭為自身串頭的子串，如 的前綴有：
後綴：以原串串尾為自身串尾的子串，如 的後綴有：

注意：字元串前後綴都不包括該串本身

給你一個文本串T(Text String)

再給你一個模式串P(Pattern String)

問該模式串是否在文本串中，怎麼找？

一開始只好分別從文本串與模式串的串頭開始逐字母比較

二者相同，再比較T串與P串的下一位

如此反復

如果一直這么順利，兩串對應位置的字元總相同，待P串中最後一個字元也匹配完畢，說明該模式串在文本串中存在，耶( •̀ ω •́ )y超開心，查找結束。但，大多數匹配過程不會如此順利，在該例中，當匹配進行至

很明顯，失配了。現在怎麼辦？按樸素思想，將P串相對T串整體右移一位，重新開始匹配，即

但這種演算法效率無疑是十分低下的。設T串長度N，P串長度M，則樸素演算法時間復雜度為O(MN)

已知的重要信息並沒有被使用——已匹配的字元串前綴

在上例中，當P串最後一個字元匹配失敗時，其已有包含七個字元的 前綴子串S 匹配成功

完全可以利用前綴子串S做點什麼。觀察到在S串

中，有相同前後綴，即下圖藍色部分

而S串各字元又與T串中對應字元相同，即有

當失配發生後，直接將P串右移四位使S串藍色後綴部分對齊T串中藍色前綴部分

從圖中紅框部分繼續嘗試匹配，發現再次失配。這次，已匹配成功的前綴串S為

而在該串中沒有相同的前後綴，只能將P串串頭移至失配處進行比較

再次失配。此時前綴串S為空串，只好如樸素演算法般將P串整體右移一位，重新開始比較

匹配成功。於是又按照之前的步驟往下匹配，直至再次失配或匹配成功

後續步驟同上，不再贅述

上述示例已展現，KMP演算法的精髓在於對已匹配成功的前綴串S的利用

在樸素演算法中，匹配失敗了，T串待匹配字元會回溯

T串原本已匹配至T[7] = 'X'，但是因為失配，需回溯到T[1] = 'b'重新開始匹配

而在KMP演算法中，若P[M]與T[K]匹配失敗，K不會回溯。既然匹配過程是從T[0]開始逐漸向右進行的，至T[K]失配發生時，T[0]至T[K-1]早已匹配過，何必再回溯過去重復匹配呢？於是乎，就如問題引入部分展示般

每當失配發生，我們總是去關注P串中已匹配成功的前綴串S

因為該前綴串是匹配成功的，說明在T串中必定存在與該前綴串相同的子串，記為S'

若S串中存在相同前後綴

則S'串必然也存在此相同前後綴

所以只需將P串右移四位，使得S串的該相同前綴對齊S'串的該相同後綴

再嘗試比較T[7]與P[3]

至於T[7]與P[3]是否能夠匹配另說（當然，本例中一看就知道沒匹配上），但通過對前綴串S的利用，成功省去了P串右移一位、兩位和三位後的無效匹配

繼續深入思考，給定一個具體的P串，其第N位的前綴串S內容是固定的，則S是否存在相同前後綴、相同前後綴的長度與內容也是確定的。換言之，對於一個具體的P串，當其與給定T串匹配至P[N]失配，P串應右移幾位再次與T串進行匹配也是確定的。我們完全可以使用一個數組記錄當P[N]失配後，應當使用N之前的哪一位再來與T串進行匹配，以此提高匹配效率，記該數組為Next數組

定義Next[i] = j表示當P串中第i位失配後，跳轉至P串第j位再次嘗試匹配

還是以之前的P串為例，它的Next數組求出來應為

取下標5為例，其前綴串為

最長相同前後綴為

若P[5]失配，應跳轉至P[1]再次嘗試匹配（最長相同前綴對應P[0]，則取其後一位P[1]，若存在多位，則取最後一位的下一位），P[5]的前一個字元P[4]對應字元'a'，而P[1]前一個字元P[0]同對應字元'a'，保證了P[1]之前字元與T串中對應字元保持匹配。所以Next[5] = 1，其餘下標對應Next數組值同如此求。

特別地，規定Next[0] = -1。而對於除下標0外的任意下標N，Next[N]的含義是 前N-1個已匹配成功的字元構成的前綴串S中，最長相同前後綴長度。 所以若在下標為N處匹配失敗了，則應前往Next[N]所對應的下標處匹配。

具體地，以下圖所示為例，P[6]與T[6]失配

而Next[6] = 2，所以使用P[2]再次嘗試與T[6]進行匹配

當求出P串Next數組後，便可快速進行與T串的匹配

現在問題只剩下如何求Next數組，注意到Next數組既然只與P串本身相關，與文本串T無關，故令P串與自身匹配即可求得

考慮字元串

其Next數組應為

令其與給定文本串相匹配

當匹配進行至

失配，於是跳轉至P[Next[3]] = P[1]處再次嘗試匹配

再度失配，也必然失配

問題在於不該出現P[N] =P[Next[N]]

若P[N] =P[Next[N]]，則P[N]失配後使用P[Next[N]]再次嘗試匹配，由於P[N] =P[Next[N]]，P[N]匹配失敗，P[Next[N]]必然也失敗

因此，若出現P[N] =P[Next[N]]情況，則令Next[N]=Next[Next[N]]

本例中該字元串新Next數組為

當匹配進行至

失配，於是跳轉至P[Next[3]] = P[0]處再次嘗試匹配

省去了之前跳轉至P[1]處的無效匹配

設T串長度M，P串長度N，由於KMP演算法不會回溯，分析易知時間復雜度為O(m+n)

對於P[N]，若其前綴串S含相同前後綴F，且F長度為n（n>1），Next[N]可以取1至n中任意值，為最大化匹配效率考慮，總是取最大相同前後綴以提高效率，節省時間

㈦ KMP是什麼的縮寫

英文縮寫：KMP

所屬分類：電子電工

英文全稱：Knuth-Morris-Pratt

縮寫簡介：一種改進的字元串匹配演算法，由D.E.Knuth與V.R.Pratt和J.H.Morris同時發現，因此人們稱它為克努特——莫里斯——普拉特操作（簡稱KMP演算法）。

㈧ kmp演算法什麼意思

KMP演算法之所以叫做KMP演算法是因為這個演算法是由三個人共同提出來的，就取三個人名字的首字母作為該演算法的名字。其實KMP演算法與BF演算法的區別就在於KMP演算法巧妙的消除了指針i的回溯問題，只需確定下次匹配j的位置即可，使得問題的復雜度由O(mn)下降到O(m+n)。
在KMP演算法中，為了確定在匹配不成功時，下次匹配時j的位置，引入了next[]數組，next[j]的值表示P[0...j-1]中最長後綴的長度等於相同字元序列的前綴。
對於next[]數組的定義如下：
1) next[j] = -1 j = 0
2) next[j] = max(k): 0<k<j P[0...k-1]=P[j-k,j-1]
3) next[j] = 0 其他
如：
P a b a b a
j 0 1 2 3 4
next -1 0 0 1 2
即next[j]=k>0時，表示P[0...k-1]=P[j-k,j-1]
因此KMP演算法的思想就是：在匹配過程稱，若發生不匹配的情況，如果next[j]>=0，則目標串的指針i不變，將模式串的指針j移動到next[j]的位置繼續進行匹配；若next[j]=-1，則將i右移1位，並將j置0，繼續進行比較。

㈨ 我不知道這么多人說的KMP什麼意思

KMP字元串模式匹配通俗點說就是一種在一個字元串中定位另一個串的高效演算法。簡單匹配演算法的時間復雜度為O(m*n);KMP匹配演算法。可以證明它的時間復雜度為O(m+n).。