前言

1.KMP演算法是什么？

2.為什么需要KMP演算法？

2.1主串找字串

2.2暴力求解

3.KMP準備作業

3.1字串的前后子串

3.2最大前后相等子串

3.3最大前后相等子串練習

4.KMP演算法

4.1簡看KMP演算法

5 Next陣列

5.1j該回溯的位置

5.2學會計算Next陣列

5.3用數學表示next陣列（重點）

5.3.1arr2[k] == arr2[j]

5.3.2 arr2[k] != arr2[j]

5.3.3 k回溯到盡頭

6.代碼實作KMP

6.1KMP外殼

6.2KMP內核

6.3KMP全部代碼

7.結語

前言

KMP演算法作為程式員的必修課之一，其抽象的程序讓初學者叫苦不迭，但是當你完全理解過后會發現其中蘊含著創造者的無窮智慧，本篇文章我將以大量的例子與圖片，為你講解這個奇妙的演算法，

1.KMP演算法是什么？

KMP演算法是一種改進的字串匹配演算法，由D.E.Knuth，J.H.Morris和V.R.Pratt提出的，因此人們稱它為克努特—莫里斯—普拉特操作（簡稱KMP演算法），KMP演算法的核心是利用匹配失敗后的資訊，盡量減少模式串與主串的匹配次數以達到快速匹配的目的，具體實作就是通過一個next()函式實作，函式本身包含了模式串的區域匹配資訊，KMP演算法的時間復雜度O(m+n) [1]

，（來自百度百科）

簡而言之就是：減少在主串找子串的程序中回退的次數，（先有個概念就行，后面會仔細講解）

2.為什么需要KMP演算法？

在回答這個問題前我們需要知道先知道兩個問題，

什么叫主串找子串？

不用kmp演算法，直接暴力求解是怎樣的？

2.1主串找字串

現在我們有主串：arr1[] = "abababc"，子串：arr2[] = “abc”，那么我們在arr1中找到arr2在其中位置的程序就叫做主串找子串，

2.2暴力求解

在暴力求解中，我們是將子串和主串逐一匹配，如果第一個字符相等就繼續匹配第二個字符，直到子串與主串全都匹配成功，就回傳子串的位置，一旦其中某兩個字符匹配不成功，主串就回到開始匹配字符的下一字符，而子串回到第一字符，

上面的話可能有一點繞，那么看了下面的圖片你就會明白暴力求解的思路，

還是這倆字串，主串：arr1[] = "abababc"，子串：arr2[] = “abc”，

（1）第一次匹配成功，第二次匹配成功，第三次匹配不成功，

（2）前面匹配失敗，第一個字串回到第二個字符'b',第二個字串回到第一個字符'a'處，

第一次匹配失敗，

（3）前面匹配失敗，第一個字串回到第三個字符'a',第二個字串回到第一個字符'a'處，

第一次匹配成功，第二次匹配成功，第三次匹配不成功，

（4）前面匹配失敗，第一個字串回到第四個字符'b',第二個字串回到第一個字符'a'處，

第一次匹配失敗，

（5）前面匹配失敗，第一個字串回到第五個字符'a',第二個字串回到第一個字符'a'處，

第一次匹配成功，第二次匹配成功，第三次匹配成功，子串走到盡頭，成功找到在第一字符串找到第二字串，

通過以上舉例可以看出，傳統的暴力求解，需要多次回溯，且第一個字串和第二個字串都需要回溯，而且例如（2）（4）步，明顯回溯過去也一定是錯的，那有沒有什么辦法讓他回溯到特定的位置，不至于像暴力求解一樣，產生許多不必要的步驟，于是就有了本篇的重點：

KMP演算法！！！

3.KMP準備作業

在學習KMP演算法之前我們還需要進行一些小小的的準備，這對你掌握KMP演算法是非常必要的，

3.1字串的前后子串

先拋開找字串的問題，拋開什么KMP演算法，我們來了解一下什么叫一個字串的前后相等子串，

--假設有這樣一個字串：a[] = "abcabcabc";

那么他的前子串的集合為：{"a","ab","abc","abca","abcab","abcabc","abcabca","abcabcab"}

看不懂？上圖！圖片順序是從左向右哦！(注：作者懶,字串的\0我沒畫😉）

--知道了什么叫前子串，那么字符的后子串也很好理解了，

他的后子串的集合為：{"c","bc","abc","cabc","bcabc","abcabc","cabcabc","bcabcabc"}

3.2最大前后相等子串

我們現在已經知道了字串a[] = "abcabcabc"的兩個資訊：

前子串的集合為：{"a","ab","abc","abca","abcab","abcabc","abcabca","abcabcab"}

后子串的集合為：{"c","bc","abc","cabc","bcabc","abcabc","cabcabc","bcabcabc"}

很明顯就可以看出前后兩個子串相等的有{"abc","abcabc"};

那最大前后相等子串就是"abcabc"，其長度為6，

3.3最大前后相等子串練習

kmp演算法的準備作業已經完成，如果你還是有點不太清楚，這里有幾個字串，你不妨可以試著找出他們的最大前后相等子串，以及長度，來加深你對前面內容的的理解，

a[] = "abcdefgh" b[] = "abcabcabcabcabc" c[] = "aba"

d[] = "hello world" e[] = "ababcabcdabcde" f[] = "abcabcdeabcabcde"

答案:

a[]:沒有最大前后相等子串    0
b[]:"abcabcabcabc"         12
c[]:"a"                    1
d[]:沒有最大前后相等子串    0
e[]:沒有最大前后相等子串    0
f[]:"abcabcde"             8

4.KMP演算法

4.1簡看KMP演算法

前面我們多次強調過，kmp演算法只需要子串回傳到特定位置，而主串不用回傳，

這到底是一個怎樣的程序呢？

還是這倆字串，主串：arr1[] = "abababc"，子串：arr2[] = “abc”，

綠色是回溯的位置，紅色是匹配結束的位置，

（1）第一次匹配成功，第二次匹配成功，第三次匹配失敗，

（2）前面不匹配失敗，主串不回溯子串回溯到第一個字符，并與上次與主串匹配錯誤的位置匹配

第一次匹配成功，第二次匹配成功，第三次匹配失敗，

（3）前面不匹配失敗，主串不回溯子串回溯到第一個字符，并與上次與主串匹配錯誤的位置匹配

第一次匹配成功，第二次匹配成功，第三次匹配成功，

看樣子KMP演算法好像就是主串不回溯，子串回溯到初始位置而已嘛，感覺并沒有說的那么強大啊，

那你可太小看KMP演算法了，我們再來看一個例子:

主串：arr1[] = "abcababcabc"，子串：arr2[] = “abcabc”，

(1)

(2)

(3)

可以很明顯的看到第二次匹配中，j并沒有回溯到字串的首位置而是回溯到字串的第三個位置

這就是我們所說的j會回溯到一個特定位置的意思，

5 Next陣列

5.1j該回溯的位置

主串：arr1[] = "abcababcabc"，子串：arr2[] = “abcabc”，

此時主串與子串在就 j = 0 位置匹配失敗，各位可以一一嘗試，我們最好的結果就是回退到 j = 2處，因為主串和子串匹配失敗一定有綠色的三個部分相等，而最大前后相等子串長度就是2即j回傳位置，

很明顯就能看出根據最大前后相等子串的一些關系，能很輕松的將一些不必要的匹配略過，只從重要位置匹配，并且不用怕匹配遺漏的問題，

5.2學會計算Next陣列

事實上，一個j會回溯的特定位置全都存放在一個Next[j] = k,陣列中，

Next[j] = k :一個用來存放子串回傳位置的陣列，回溯的位置用字母k來表示，（Next只與主串和子串匹配錯誤的位置，以及子串本身有關，與主串沒有太大關系，所以后面我們將拋棄主串，只講子串，）

那回溯位置k是怎么求的呢？

1.從匹配失敗位置，找到他前面的字串的最大前后相等子串長度，

2.默認第一個k值為-1(Next[0] = -1),第二個k值為0(Next[1] = 0),我們只需要從第三個k值(Next[2])開始求，(這里不同的書籍或人規定的默認值有所不同）

知道了Next陣列的規則，我們開始求他了，假設我們有這樣一個子串，

arr2[11] = "abcababcabc"

Next [] ={ -1, 0 , ? , ? , ? , ? , ....... }

（1）假設我們此時的子串與主串在 j = 2 時匹配失敗，

綠色代表需要找最大前后相等子串長度的字串，橙色數字代表該字串的最大前后相等子串長度

（2）假設我們此時的子串與主串在 j = 3 時匹配失敗，

（3）假設我們此時的子串與主串在 j = 4 時匹配失敗，

（4）假設我們此時的子串與主串在 j = 5 時匹配失敗，

（5）假設我們此時的子串與主串在 j = 6 時匹配失敗，

（6）假設我們此時的子串與主串在 j = 7 時匹配失敗，

（7）假設我們此時的子串與主串在 j = 8 時匹配失敗，

（8）假設我們此時的子串與主串在 j = 9 時匹配失敗，

（9）假設我們此時的子串與主串在 j = 10 時匹配失敗，

到此我們有：Next[i] = { -1 , 0 , 0 , 0 , 1 , 2 , 1 , 2 , 3 , 4 , 5 }

根據這樣的規則，我們就得到了一個包含子串每一位錯誤時對應的退回位置k的陣列，這個陣列叫做Next，而且能知道，next陣列的長度與子串的長度相同，

--Next陣列計算練習

1.a[] = "ababcabcdabcde"

2.b[] = "abcabcabcabcdabcde"

答案：

a[]:   a b a b c a b c d a b c d e
      -1 0 0 1 2 0 1 2 0 0 1 2 0 0

b[]:   a b c a b c a b c a b c d a b c d e
      -1 0 0 0 1 2 3 4 5 6 7 8 9 0 1 2 3 0

5.3用數學表示next陣列（重點）

通過前面的學習，你應該已經知道怎么求Next陣列了，但那是你用眼睛去看出來的Next陣列而不是用推匯出來的Next陣列，當計算機拿到一個子串，除了默認值設定的Next[0] = -1,Next[1] = 0,其他什么都不知道，Next陣列后面的每一位都需要我們去設計計算出來，

5.3.1arr2[k] == arr2[j]

arr2[] = "abcababcabc"

假設我們已知Next = { -1 , 0 , 0 , 0 , 1 , 2 , 1 , 2 , 3 ,? }，需要求解Next[9] = ?，

此時令j = 8那已知資訊就有 arr[j] = 'a'，Next[j] = k = 3, arr[k] = 'a',此時arr[j] = arr[k]

那么: { arr2[ 0 ] , ... , arr2[ k - 1 ] } = "abc" { arr2[ x ] , ... , arr2[ j - 1 ] } = "abc" 即Next [ j ] = k = 3的原因

根據兩組下標可知：(k-1) - 0 = (j - 1) - x ,所以 x = j - k ，

將x帶回到第二組的下標中: { arr2[ 0 ] , ... , arr2[ k - 1 ] } = "abc" { arr2[ j - x ] , ... , arr2[ j - 1 ] } = "abc"

又因為arr[j] = arr[k] : { arr2[ 0 ] , ... , arr2[ k - 1 ] , arr2 [ k ] } = "abca" { arr2[ j - x ] , ... , arr2[ j - 1 ] , arr2 [ j ] } = "abca"

所以可知：Next [ j + 1 ] = k + 1 = 4 ！！！！！！！！！！！！！！

注意1：一定要記住k就是最大前后相等子串長度，

結論1：arr2[k] == arr2[j] ? Next [ j+1 ] = k + 1

5.3.2 arr2[k] != arr2[j]

前面我們已經知道了當arr2[k] == arr2[j]，怎么求Next[ j + 1 ] ，現在我們再來看看當 arr2[k] != arr2[j]的情況

arr2[] = "abcababcabc"

假設我們已知Next = { -1 , 0 , 0 , 0 , 1 , 2 , ？ }，需要求解Next[6] = ？，

此時令j = 5那已知資訊就有 arr[j] = 'a'，Next[j] = k = 2, arr[k] = 'c',此時arr[j] != arr[k]

那我們就讓新的 k = Next[ k ] = 0，

此時我們又有已知資訊 arr[j] = 'a'，Next[j] = k = 2, arr[k] = 'a',arr[j] = arr[k]

一些細心的讀者可能會發現，現在又成了前一種情況arr[j] == arr[k]，

因此我們要求解的 Next[ j + 1 ] 根據之前推導的公式Next[ j + 1] = k + 1 ? Next [ j + 1 ] = 1，

注意2：此時的 k 已經被改變過了，是新的k，

結論2：arr2[k] != arr2[j] ? Next[ j+1 ] = k + 1

5.3.3 k回溯到盡頭

一些讀者可能又會提出疑問：我的例子太特殊，要是k一直往Next陣列前面走，走到第一個元素都找不到相等呢？

一直都找不到，那我們此時k肯定回溯到了陣列頭部，即k = - 1處，那我們就停止回溯， Next [ j + 1 ] = k + 1 ? Next [ j + 1] = 0，

結論3：k == -1 ? Next[ j+1 ] = k + 1 ，即Next[ j + 1 ] = 0，

以上就是KMP的精華所在，創造者成功的找到了高效回溯的之中存在的潛藏規律，這下你們大概能理解為什么KMP演算法如此令人著迷了吧，

6.代碼實作KMP

至此，如果你將前面的內容都理解了，那你基本把KMP演算法掌握的差不多了，只剩如何用代碼寫出來的問題，下面我會分為兩個部分講解，有一定基礎的讀者也可以先嘗試自己寫一寫，等遇到問題再回來看看我的代碼與你的有何區別

6.1KMP外殼

現在我們不去管如何用代碼得到Next陣列，而是將Next陣列當作已知，嘗試通過寫出KMP演算法的外殼，

這里有三個要點：

1.主串不回退

2.子串回退到一個特殊的位置（通過前面我們已經知道，回退的特殊位置就是Next[ j ] = k

3.假設Next陣列已知

代碼如下：

#include<stdio.h>
#include<string.h>
int KMP(char* arr1, char* arr2)
{
	int i = 0;											//不需要記錄匹配的首位置，
	int j = 0;                                          //因為kmp演算法i不需要回溯
	
	int len1 = strlen(arr1);
	int len2 = strlen(arr2);
	
	int Next[len2] = {0};                               //假設Next已經得到，其長度為子
                                                        //串的長度
	
	if (len1 == 0 && len2 == 0 || len2 == 0)            //當arr1與arr2都為慷訓arr1為空
        return 0;                                       //時直接返回
	
    else if (len1 == 0 || len2 > len1) 		            //當arr1為慷訓者第二個字串比
        return -1;                                      //第一個字串長，不可能找到
	
	while (i < len1 && j < len2)						//當arr1和arr2都沒走到盡頭
	{
		if (arr1[i] == arr2[j])
		{
			i++;
			j++;
		}
		else
		{
			j = Next[j];						        //當主串與子串不同時j回溯到 
                                                        //Next[j]，i不用回溯
		}
	}
	if (j >= len2)
		return i - j;							        //如果子串走到盡頭，代表找到了 
                                                        //回傳開始匹配時的位置
	
    return -1;											//否則就是主串走到盡頭，代表沒
                                                        //找到
}

6.2KMP內核

前面的代碼相信大部分人都能夠輕松完成，就是簡單的對暴力求解進行了一點改造而已，那接下來我們去用代碼求得Next陣列，

這里我們只需要借助我們前面推出來的三個結論：

結論1：arr2[k] == arr2[j] ? Next[ j+1 ] = k + 1 k不往子串前走

結論2：arr2[k] != arr2[j] ? Next[ j+1 ] = k + 1 k往子串前走

結論3：k == -1 ? Next[ j+1 ] = k + 1 k走到子串盡頭

注意：雖然三個結論看起來相似，但一定要記住每個k分別是什么意思

代碼如下:

void GetNext(int* Next, const char* arr2)           //傳入Next陣列地址，傳入子串首地址
{
	int j = 1;										//初始已知項 j = 1
	int i = j + 1;									//初始待求項 j+1 = 2
	int k = 0;                                      //待求的Next[j+1]前一項的k值
	
	int len2 = strlen(arr2);                        //子串長度
	
	Next[0] = -1;									//Next陣列前兩個默認值
	Next[1] = 0;
	
	while (i < len2)                                //當待求項走到arr2盡頭,k全求出
	{
		if ((k == -1) || arr2[k] == arr2[i - 1])	//結論1，結論3情況
		{
			Next[i] = k + 1;
			k = k + 1;                              //待求的Next[j+1]前一項的k值
			i++;                                    //待求項往后走一位
		}
		else
		{
			k = Next[k];							//結論2情況
		}
	}
}

6.3KMP全部代碼

前面的代碼很明顯只將兩個部分單獨寫出，并沒有做出聯系，因此還需要一些改動，

#include<stdio.h>
#include<string.h>

void GetNext(int* Next, const char* arr2)           //傳入Next陣列地址，傳入子串首地址
{
	int j = 1;										//初始已知項 j = 1
	int i = j + 1;									//初始待求項 j+1 = 2
	int k = 0;                                      //待求的Next[j+1]前一項的k值
	
	int len2 = strlen(arr2);                        //子串長度
	
	Next[0] = -1;									//Next陣列前兩個默認值
	Next[1] = 0;
	
	while (i < len2)                                //當待求項走到arr2盡頭，找完Next陣列
	{
		if ((k == -1) || arr2[k] == arr2[i - 1])	//結論1，結論3情況
		{
			Next[i] = k + 1;
			k = k + 1;                              //待求的Next[j+1]前一項的k值
			i++;                                    //待求項往后走一位
		}
		else
		{
			k = Next[k];							//結論2情況
		}
	}
}

int KMP(char* arr1, char* arr2)
{
	int i = 0;											//不需要記錄匹配的首位置，
	int j = 0;                                          //因為kmp演算法i不需要回溯
	
	int len1 = strlen(arr1);
	int len2 = strlen(arr2);
	
	int* Next = (int*)malloc(len2 * sizeof(int));       //為Next陣列開辟一個與子串一樣長的 
                                                        //空間
	
	GetNext(Next, arr2);                                //借用Next函式得到Next陣列的內容

	if (len1 == 0 && len2 == 0 || len2 == 0) return 0;	//當arr1與arr2都為慷訓arr1為空時直 
                                                        //接回傳

	else if (len1 == 0 || len2 > len1) return -1;		//當arr1為慷訓者第二個字串比第一 
                                                        //個字串長
	
	while (i < len1 && j < len2)						//當arr1和arr2都沒走到盡頭
	{
		if (arr1[i] == arr2[j])
		{
			i++;
			j++;
		}
		else
		{
			j = Next[j];						        //當主串與子串不同時j回溯到 
                                                        //Next[j]，i不用回溯
		}
	}
	if (j >= len2)
		return i - j;							        //如果子串走到盡頭，代表找到了回傳 
                                                        //開始匹配時的位置
	return -1;											//否則就是主串走到盡頭，代表沒找到
}

int main()
{
	char arr1[] = "abababcabc";         //測驗用             
	char arr2[] = "abcabc";
	char pos;
	pos = KMP(arr1, arr2);
	printf("%d", pos);
}

7.結語

寫下這篇博客，不單單是教大家，同時也是我自己的一個學習總結，如果各位學到了東西，還請不要吝惜你們的點贊收藏，這也將激勵我寫出更好的文章，

特別鳴謝：

@位元大博哥，如果大家看了我的視頻還是有所不懂可以看大博哥的視頻b站：BV1UL411E7M8

轉載請註明出處，本文鏈接：https://www.uj5u.com/qita/301526.html

標籤：其他

上一篇：常見排序之近線性排序

下一篇：資料結構：如果寫代碼，就寫一棵樹

KMP演算法詳解——多圖，多例子（c語言）

前言

1.KMP演算法是什么？

2.為什么需要KMP演算法？

2.1主串找字串

2.2暴力求解

3.KMP準備作業

3.1字串的前后子串

3.2最大前后相等子串

3.3最大前后相等子串練習

4.KMP演算法

4.1簡看KMP演算法

5 Next陣列

5.1j該回溯的位置

5.2學會計算Next陣列

5.3用數學表示next陣列（重點）

5.3.1arr2[k] == arr2[j]

5.3.2 arr2[k] != arr2[j]

5.3.3 k回溯到盡頭

6.代碼實作KMP

6.1KMP外殼

6.2KMP內核

6.3KMP全部代碼

7.結語