文章目錄

• 一、問題背景（文本匹配）
• 二、一般思路（暴力匹配）
• • 1.動畫展示
  • 2.步驟說明
  • • 步驟一
    • 步驟二
  • 3.代碼實現
• 三、KMP
• • 1.動畫展示
  • 2.步驟說明
  • • 步驟一
    • 步驟二
  • 3.$Next$說明以及$j=Next[j]$的合理性解釋
  • 4.比較異同
  • 5.代碼實現
• 四、$Next$遞推求解
• • 1.方法說明（若已知$Next[0,j?1]$,如何求$Next[j]$）
  • 2.代碼
• 五、$Next$遞推求解改進
• • 1.缺陷
  • 2.方法說明
  • 3.代碼

---

一、問題背景（文本匹配）

當前有一個文本串$S$，長度為$n$

再給定一個模式串$P$，長度為$m$

要求給出模式串在文本串中第一次匹配的起始位置。

---

二、一般思路（暴力匹配）

1.動畫展示

2.步驟說明

設$i$為文本串$S$上的位置下標，$j$為模式串$P$上的位置下標，$ij$初始值均為$0$

步驟一

判斷此時的$ij$是否超出各自字符串的限制，若$j$超出$P$的限制則退出并返回匹配成功處的位置下標，若$i$超出$S$的限制，則退出并說明無解；
再比較$S[i]$與$P[j]$，若$S[i]==P[j]$，則$i++,j++$，重復步驟一；
若$S[i]\ne P[j]$，進入步驟二；

步驟二

$i=i?j+1$
$j=0$
返回步驟一

3.代碼實現

int match_vio(char *P,char *S){int n=strlen(S),i=0;int m=strlen(P),j=0;while(j<m&&i<n){if(S[i]==P[j]){i++;j++;}else{i-=j-1;j=0;}}if(j==m)return i-j;else return -1; }

---

三、KMP

1.動畫展示

2.步驟說明

步驟一

判斷此時的$ij$是否超出各自字符串的限制，若$j$超出$P$的限制則退出并返回匹配成功處的位置下標，若$i$超出$S$的限制，則退出并說明無解；
再比較$S[i]$與$P[j]$，若$S[i]==P[j]$或者$j==?1$，則$i++,j++$，重復步驟一；
若$S[i]\ne P[j]$，進入步驟二；

步驟二

$i$不變
$j=next[j]$
進入步驟一

3.$Next$說明以及$j=Next[j]$的合理性解釋

$Next$表示代表當前字符之前的字符串中，字符串最長公共前綴后綴長度，假設其長度為$n$,則存在$n$個前綴與$n$個后綴，我們舍去其中長度為$n$的情況，則剩下$n?1$個前綴與$n?1$個后綴，前綴與后綴的最大匹配也就是該字符串的最長公共前綴后綴長度。

由上可知，$Next$的最小值就是$0$（不包括第一個位置的$?1$）

比如說當前字符串為$ABCDAB$
則有：

為什么此時可以不移動$i$，只改變$j$，中間是否有可能出現遺漏？（$j=Next[j]$的合理性解釋）

在任一時刻，都滿足$S[i?j,i)==P[0,j)$，也就是我們已經知道了$S[i?j,i)$的所有信息：

一旦比對失敗，我們就可以知道哪些位置值得比對或者不必比對

而$Next[j]$正是這一思想的踐行
由于$Next$值是當前位置前字符串的最長公共前綴后綴長度，這個值的確認只與模式串有關，與文本串無關，可以事先確定
當失配時，$j=Next[j]$，充分利用已知信息，找出模式串中最值得再次匹配的位置

4.比較異同

最大的區別在于步驟二的處理，之前暴力匹配中需要同時移動$ij$，但此時$kmp$算法只需改變$j$，而$kmp$算法中$j$最壞的結果也就只是變為$0$，所以從整體上來看，$kmp$算法時間復雜度為$O(n+m)$（后面會介紹關于$O(m)$為Next數組建立的時間復雜度）,暴力匹配時間復雜度為$O(nm)$，所以明顯$kmp$更優。

其次的區別是關于條件的變化，暴力匹配中僅當相等時，而$kmp$中當$j==?1$同樣作為條件，$j==?1$的實際作用是當$j==0$時文本串與模式串失配（模式串的第一位都對不上），我們將$j$置為-1，從而經過使得模式串的第一位可以與文本串的下一位進行比對。

5.代碼實現

int match_kmp(char *P,char *S){int *next=buildNext(P);int n=strlen(S),i=0;int m=strlen(P),j=0;while(j<m&&i<n){if(j==-1||S[i]==P[j]){i++;j++;}else{j=next[j];}}delete [] next;if(j==m)return i-j;else return -1; }

---

四、$Next$遞推求解

1.方法說明（若已知$Next[0,j?1]$,如何求$Next[j]$）

從定義出發，$Next[j]$表示的是$P[0,j)$中最長公共前綴后綴長度，而我們已知$Next[0,j?1]$
我們令$t$表示$Next[j?1]$
若$P[j]==P[t]$，表示上一次前綴與后綴的下一位同樣是匹配的，所以此時的$Next[j]=Next[j?1]+1$，也就可以寫為:$Next[++j]=++t$；為了避免越界，當$t==?1$時，同樣進行這一步操作，而且所得結果依然符合$Next$數組
若$P[j]\ne P[t]$，表示表示上一次前綴與后綴的下一位不是匹配的，通過$t=Next[t]$的操作，回溯到再上一次匹配的前后綴，繼續比對，直至$t==?1$或找到合理的匹配

遞推解釋

2.代碼

int * buildNext(char *P){int m=strlen(P),j=0;int *N=new int [m];int t=N[0]=-1;while(j<m-1){(t==-1||P[j]==P[t])?N[++j]=++t:t=N[t];}return N; }

---

五、$Next$遞推求解改進

1.缺陷

出現了連續的比對失敗，原因？
當$P[3]\ne S[3]$時，根據$KMP$算法的思路就是用$P[Next[3]]$與$S[3]$進行比對，由于此時滿足$P[Next[3]]==P[3]$，所以比對的結果依然為失配；
當$P[3]==S[3]$時，不必考慮這些

2.方法說明

根據上文，接下來要做的就是對$P[Next[j]]==P[j]$的情況進行處理，避免無必要的比對
若出現了$P[Next[j]]==P[j]$的情況，我們就令$Next[j]=Next[Next[j]]$，讓它等于再上一位的值，根據遞推關系，其實這樣也就避免了所有的重復

3.代碼

int * buildNext_2(char *P){int m=strlen(P),j=0;int *N=new int [m];int t=N[0]=-1;while(j<m-1){if(t==-1||P[j]==P[t]){j++;t++;N[j]=(P[j]!=P[t])?t:N[t];}else t=N[t];}return N; }

---

總結

以上是生活随笔為你收集整理的KMP讲解（自制动图）的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。