【概述】

KMP 是在 MP 算法的基礎上改進出來的，兩者的核心思想與匹配過程相同，唯一不同的是在于 next 數組的求法，其目的是為了避免 MP 算法中明顯失敗的匹配。

KMP 算法又稱?Knuth-Morris-Pratt 字符串匹配算法，是由于 D.E.Knuth、J.H.Morris 和 V.R.Pratt 三人共同研究的，用于解決字符串匹配問題。

其核心思想是利用已經部分匹配的有效信息，來保持文本串指針不回溯，通過修改模式串指針，讓模式串盡量地移動到有效的位置，因此，整個 KMP 的重點就在于當模式串中某個字符與文本串不匹配時，如何移動模式串指針。

KMP 算法的主要特點是：

需要對模式字符串做預處理；

預處理階段需要額外的 O(m) 空間和復雜度；

匹配階段與字符集的大小無關；

匹配階段至多執行 2n-1 次字符比較；

對模式中字符的比較順序時從左到右；

【算法原理】

如下圖，以文本 T=ABACBCDHIJK，模式 P=ABAD 為例，前面三個字符是匹配的而 C 與 D 不匹配，可以利用已匹配的信息將模式指針 j 移到第 1?位上（指針從 0 開始），文本指針 i 位置不變

同理，對于下圖中的文本 T=ABCABCDHIJK 與模式 P=ABCABB，當 C 與 B 不匹配時，可利用已匹配信息，將模式指針 j?移動到第 2?位上，文本指針 i 位置不變

通過上面兩個例子，可以看出，當匹配失敗時，文本指針 i 的位置不變，模式指針 j 要移動到位置 k，而位置 k 的性質滿足：模式串最前面 k 個字符與?j 之前的最后 k 個字符相同，即：

當??時，有：

根據

可得：，因此可以判斷直接將 j 移動到 k 無須再比較前面的 k 個字符

至此，關鍵的部分是求得 k，由于在模式 P 的每一個位置都可能發生不匹配，也就是說需要計算每一個位置 j 對應的 k，故而可以用一個數組 next[] 來保存，即令 next[j]=k 表示當 T[i]!=P[j] 時，j 指針的下一個位置

以下圖為例，可以發現，當 j 為 0 時就不匹配，這個時候 j 已經在最左邊了，不可能進行移動，需要調整的是將指針 i 后移一位，因此要對 next[] 數組初始化，即 next[0]=-1

再以下圖為例，當 j=1 時不匹配，因為他前面只有一個位置，那么顯然指針 j 需要移到 0 位置

對比以下兩個圖，可以發現，當? 時，有?next[j+1]=next[j]+1

證明：

由于 P[j] 之前已經有?，即

這個時候有 P[k]=P[j]，那么可以得到?

即：，即：，從而有：

而當??時，對比以下兩張圖，可以發現只要令 k=next[k] 即可

—————以上內容為 MP 的 next 數組，以下內容為 KMP 的 next 數組 —————

此時，next 數組已經求出，但還存在一個缺陷

以下圖為例，顯然得到的 next 數組是 {-1,0,0,1}

如下圖，當 C 與 B 不匹配時，應將模版指針 j 移動到第一個元素

不難發現，由于后面的 B 已經不匹配了，那么前面的 B 也一定是不匹配的，因此這一步完全沒有意義，同理，A 也一樣

顯然，發生問題的原因在于 P[j]=P[next[j]] ，因此加一個判斷條件即可，值得注意的是，何時需要加上此條判斷要根據實際情況

【應用】

KMP 算法的核心是求 next 數組，最大的應用除解決字符串匹配問題外，常用 next 數組來求循環節。

在未加判斷的 next 數組中，其代表當前字符之前的字符串中，最大前綴與后綴匹配數，即 next[j]=k 代表 j 之前的字符串中有最大長度為 k 的相同前綴后綴。

例如：

i	0	1	2	3	4	5
p[i]	a	b	c	b	a	?
next[i]	-1	0	0	0	0	1

對于長度為 n 的模式串，由于?next[j]=k 表示 p[1...i-1] 最大前綴與后綴匹配數，那么模式串第 1 位到 next[n] 位與模式串第 n-next[n] 位到第 n 位是匹配的

因此當?next[i]>0 時，i-next[i] 為字符串匹配的時候移動的位數，故而當?n%(n-next[n])=0 時，說明模式串中存在重復連續的子串，其長度為 len=n-next[n]，那么字符串的最小周期?res=n/len=n/(n-next[n])

【算法實現】

1.求 next 數組

1）MP版

int next[N]; void getNext(char p[]){next[0]=-1;//初始化int len=strlen(p);//模式串長度int j=0;//模式指針jint k=-1;//位置kwhile(j<len) {if(k==-1||p[j]==p[k]) {//next[j+1]=next[j]+1k++;//此前有next[j]=kj++;//指針后移next[j]=k;}else{k=next[k];}} }

2）kmp版

int next[N]; void getNext(char p[]){next[0]=-1;//初始化int len=strlen(p);//模式串長度int j=0;//模式指針jint k=-1;//位置kwhile(j<len) {if(k==-1||p[j]==p[k]) {//next[j+1]=next[j]+1k++;//此前有next[j]=kj++;//指針后移if(p[j]==p[k])//當兩個字符相等時跳過next[j] = next[k];elsenext[j]=k;}else{k=next[k];}} }

2.匹配

int KMP(char t[],char p[]) {int tLen=strlen(t);//文本串長度int pLen=strlen(p);//模式串長度int i=0;//文本串指針int j=0;//模式串指針getNext();//獲取next數組while(i<tLen&&j<pLen) {if (j==-1||t[i]==p[j]){//當j為-1時，要移動的是i，同樣j也要歸零i++;j++;}else{j=next[j];//j回到指定位置}}if(j==pLen)//最終當模式串的位置與模式串的長度相同時，說明匹配成功return i-j;else//匹配失敗return -1; }

3.求模式串出現次數

int KMP(char t[],char p[]) {int tLen=strlen(t);int pLen=strlen(p);getNext(p);int res=0;int j=0;//初始化在模式串的第一個位置for(int i=0;i<tLen;i++){//遍歷文本串while(j&&p[j]!=t[i]){//順著失配邊走，直到可以匹配，最壞情況是j=0j=Next[j];}if(p[j]==t[i]){//匹配成功，繼續下一個位置j++;}if(j==pLen){//計算模式串在文本串中出現的次數res++;/*若可使用重復字符，j=0需注釋掉若不可使用重復字符，j=0無需注釋原因：是否需要初始化模式串位置*/j=0;}}return res; }

4.求最小循環節長度

int next[N]; void getNext(char p[]){next[0]=-1;//初始化int len=strlen(p);//模式串長度int j=0;//模式指針jint k=-1;//位置kwhile(j<len) {if(k==-1||p[j]==p[k]) {//next[j+1]=next[j]+1k++;//此前有next[j]=kj++;//指針后移next[j]=k;}else{k=next[k];}} } int main(){scanf("%s",p)；int n=strlen(p);//模式串長度getNext();//獲取next數組int len=n-next[n];//與前綴相同的后綴長度if(n%len==0){//存在循環節int res=n/len;//循環節長度printf("%d\n",res);}else//不存在循環節，長度為1printf("1\n");return 0; }

總結

以上是生活随笔為你收集整理的字符串处理 —— 单模式匹配 —— MP 算法与 KMP 算法的全部內容，希望文章能夠幫你解決所遇到的問題。

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