目录

前言

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算法的@R_723_1304@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"}

看不懂？上图！图片顺序是从左向右哦！(注：作者懒,字符串的我没画😉）

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

他的后子串的集合为：{"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 &amp;& 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