devbox
很楠不爱3
这个屌丝很懒，什么也没留下！
关注作者
热门标签
热门文章
当前位置:   article > 正文

算法(一)|九千字硬核讲解KMP算法，搞懂KMP的来龙去脉

作者：很楠不爱3 | 2024-05-17 10:31:52

赞

踩

kmp

目录

0.前言

1.KMP算法简介

2.字符串匹配问题

BF算法(Brute-Force)

 代码实现

BF的时间复杂度

BF算法的缺陷

BF算法改进的可能性

3. KMP算法

1）KMP算法原理

2）问题引入

3）问题分析

a. 主串不匹配的字符串中间可能包含匹配的子串吗

b. 指针i可以不回溯吗

c.如何判断si有没有匹配成功的可能性

4）算法推导

确定k的范围

对信息深挖掘

算式求解

k与哪些因素有关系

5)代码实现

4.KMP算法的时间复杂度推导

1）next数组最坏情况

2）主串数组匹配的最坏情况

 5.KMP算法的优化

  6.学习KMP算法的感受

0.前言

很喜欢弗赖登塔尔这一句话，第一次是出现在我的大学微积分课堂的第一课，就给我留下了深刻的印象

没有一种数学思想， 以它被发现时的那个样子发表出来。一个问题被解决以后， 相应地发展成一种形式化的技巧，结果使得火热的思考变成了冰冷的美丽。

弗赖登塔尔(H.Freudenthal,荷兰)

 本文有大量的数学推导，自己不懂的时候，可以动一动笔，自己思考一下，会有不一样的收获。如果有问题，欢迎大家对我批评指正，互相学习

1.KMP算法简介

KMP算法是三位学者(Knuth、Morris and Prat)在 Brute-Force算法的基础上提出的模式匹配的改进算法。KMP的核心原理是利用匹配字符串的信息，当比较出现错误时，不回溯主串的指针，而是利用匹配字符串的信息将匹配字符串的指针指向相应位置，从而大大减少时间。

2.字符串匹配问题

如果我们想在一个字符串S(主串)中查找另外一个字符串T(模式匹配串)，看看主串S有没有包含子串T（例如图中S和T查找）。我们很容易想到BF算法()

BF算法(Brute-Force)

BF算法简单来说就是挨个比较每个字符，如果比较出错，主串回到比较开始的下一个位置,子串回到第一个位置继续比较，由此遍历比较，是暴力算法。

 

 代码实现

  1. #include <string.h>
  2. //BF算法 暴力算法
  3. //用i索引和j索引求解
  4. char* Index_BF(const char* str,const char* find)
  5. {
  6. 	int slen = strlen(str);
  7. 	int flen = strlen(find);
  8. 	if (slen < flen) //如果查找的字符串还更长，直接返回NULL
  9. 		return NULL;
  10. 	int i = 0, j = 0;
  11. 	while (i < slen && j < flen)
  12. 	{
  13. 		if (str[i] == find[j])
  14. 		{
  15. 			i++;
  16. 			j++;
  17. 		}
  18. 		else //如果字符不匹配，则i指针返回到之前的下一个位置,j重置为0
  19. 		{
  20. 			i = i - j + 1;
  21. 			j = 0;
  22. 		}
  23. 	}
  24. 	return (j == flen) ? str + i-j : NULL; //j==flen由此来判断是否查找到
  25.  
  26. }

BF的时间复杂度

BF的算法复杂度很容易想到，最坏的情况(极限情况)是每一次比较子串，都刚好是最后一个字符出错，由此复杂度为O(m*n）,m为主串s的长度，n为模式匹配串t的长度，算法时间复杂度大。

BF算法的缺陷

BF算法当每一次比较出现失败时，主串指针i都会回溯到比较开始的下一个位置，该位置可能会被再次比较。所有比较都完成时，某位置可能会被比较过多次，某些比较操作显得多余。BF算法并没有充分利用信息。

BF算法改进的可能性

BF主要缺陷在于，当比较失败的时候，主串s的指针i回溯到开始的下一个位置，但是该位置被比较过一次，可以通过匹配子串t的信息知道主串该位置的字母是什么，也就是说匹配失败前面的字符都是在子串t里面的，可以通过子串t来判断信息。如果比较失败时，主串s的指针i不回溯，而是通过子串t的信息来判断si应该与子串的某个位置k进行比较，这样是有改进的可能。这是因为主串指针i前面的字符被比较过，字符都出现在子串t里，相当于指针i的前面的信息被储存在子串t内，可以进行挖掘。

3. KMP算法

1）KMP算法原理

KMP算法是改进的BF算法，基础是BF算法，原理是利用匹配字符串的信息，当比较出现错误时，不回溯主串的指针，而是利用匹配字符串的信息将匹配字符串的指针指向相应位置。

2）问题引入

在主串s中查找子串t的位置，匹配过程中主串的s索引为i与子串t的索引为j的字符匹配出现错误，如图所见(能匹配，说明i>j）

3）问题分析

主串s的第i个字符与匹配串t的第j个字符匹配出现问题，说明si是不等于tj的，同时也说明，之前比较的字符串是相等的，即主串的第i-j-1个位置到第i-1个位置的字符串与匹配串的第0位置到第j-1个位置是匹配的。

这是因为字符不匹配而得到的已知条件

在BF算法改进的分析过程中，我们可以通过模式串t知道主串s中索引为i-j-1到i-1之间的字符串的各字符，这是通过字符串匹配而知道的信息。下一步就是更正指针i和指针j的比较位置。现在我们想以下的问题

a. 主串不匹配的字符串中间可能包含匹配的子串吗

不匹配的字符串不可能包含匹配的子串t，因为匹配的字符串长度(j-1)没有匹配的子串t长，所以主串索引为i-j-1到i-1是不可能包含子串t。但是可能会含有匹配成功的字符串的部分串，如果是这种情况，该串一定包含索引为i的字符

b. 指针i可以不回溯吗

对于主串s指针i下一个指向的位置肯定是在i-j-1之后。根据上面一个问题分析，我们可以知道，匹配错误的串中是不可能包含匹配串t的，但可能包含匹配成功串的头指针位置，这种情况，匹配成功的串一定会包含s。由此分析我们可以知道，当si和tj匹配错误时，只有两种情况，第一种情况比较si和模式串t中的某个字符，来继续进行比较；第二种情况,si不用于t字符串任意进行比较(si不可能匹配成功)，而是比较si+1和t0的字符，继续进行比较。由此可见，指针i不必回溯，不会漏掉结果，就能够包含所有情况。

比较si+1和t0是因为不知道si+1是什么字符，没有比较过，和BF算法是一样的。现在问题是如何判断si有没有匹配成功的可能性?

c.如何判断si有没有匹配成功的可能性

怎样算匹配成功呢？首先，匹配成功的串肯定是在主串是连续的，而且串是与模式串t是一样的。由前面分析，我们可以知道匹配错的串之间可能包含有匹配成功的串的起始位置，si也有可能作为匹配成功串的起始位置，这两种情况的匹配成功的串都会包含si，si一定和t串中的某位置k进行比较。因为si前边的位置是知道的，因此前边是否匹配是不用判断就可以知道，假如是能够匹配的，则判断si与tk是否相等，如果相等，则有匹配的可能，如果不等则si不可能匹配成功。还有一种情况，是匹配错的串之间不可能有匹配成功的可能，而且比较si与t0也不相同，si不可能匹配成功，如下图。

由以上分析可以知道，当si与tj匹配失败时，匹配错误的串是不可能包含模式串，可以不回溯i指针，让si与t串的索引为k的字符再次进行比较，如果相等，则字符si有匹配成功的可能，如果不相等，字符si不可能匹配成功。这种算法的可能性是因为，匹配错误的串是可以通过模式串t知道相关信息

4）算法推导

假设主串si与tj匹配失败时，si应该与tk进行再比较，由匹配失败的信息我们可以知道si-j到si-1的字符串信息，应该满足以下关系

 因为si与tk进行比较，说明tk前面的字符从t0到tk-1的字符与si前面的字符匹配成功，所以应该有上述的条件。

确定k的范围

k的范围是什么呢，k可能大于j吗？k不可能大于j，如果k＞j，说明si与t串后面的字符进行了比较，这就说明tk之前的字符都匹配成功，长度显然是不一样的，与比较的事实相违背，因此k是不可能大于j的；k有可能等于j吗？事实情况是si不与tj相匹配，所以k不可能等于j。由此我们可以得出k的范围是： 0<=k<j，是在j的左边。

对信息深挖掘

对k的范围的讨论，我们知道k<j的，也就是说si-k到si-1的长度是小于si-j到si-1的长度的，说明si-k到si-1是si-j到si-1的子串，如下图

 因为k<j，可以有以下的推导

 这时，信息已经挖掘的差不多了，能利用上的已经利用上了，我们重新梳理一下，我们通过已知信息因为si与tj匹配错误得出了关系式，我们已经知道主串s，模式串t，指针i和指针j的位置，如何求出k？是关键问题，如果求出了k的表达式，则不用回溯指针i，就可以完成匹配。

算式求解

我们可以用递归的思路求解，这样求解过程比较简单，本文用递归思路讲解求解过程,接下来我们再想个问题

k与哪些因素有关系

k只与模式串和模式串的位置有关，与主串没有任何关系。k的意义是，当主串中si与tj匹配发生错误时，应当将si与tk再进行比较，看是否能够匹配成功，也就是说tk前面的字符与si前面的字符是匹配成功的，而且也是可以通过子串能够知道si前面匹配成功的串的信息，主串是怎样组成的，没有任何关系。也可以由前面的推导公式看出来，k只与模式串与j有关，只要满足下列关系，就可以让si与tk进行比较，因此k只与模式串和模式串的位置有关，与主串没有任何关系。

 这样看来，k好像就是模式串t的自身属性，由模式串t和比较位置j所决定，与主串s无关。我们令这种属性为next数组，数组的长度与模式串t相同，next数组的意义是当tj与主串si发生匹配错误时，si应该与t总索引为next[j]的字符进行比较。为了包含所有情况,上述讨论的情况是si会发生匹配成功的可能，但si可能不会匹配成功，如果前面的字符串不匹配模式串，并且si与t0进行比较也不相等，那这个时候就要让si+1与t0进行比较，比较si就没有任何意义，令这种情况的next[j]为-1,也就是比较si+1和t0,这种情况，如下图

索引j012345
模式串tabaabc
next[j]-100112

 比如，对于模式串abaabc,如果是索引为4的位置匹配错误，我们通过匹配信息可以知道，比对的上一个位置的字符肯定是a（这是通过模式串信息知道的），直接让si-1与t0进行匹配，只需要比较si与t1的位置，如果si与t1匹配成功，则继续比较下一个位置，如果不成功，还可以通过这次匹配的信息知道前几个字符，再继续比较，直到匹配结束。

 

 

假设我们已经确定了，当主串si与tj匹配发生错误时，si应该与tk进行比较，k的值是已知的，则有下列关系

因为k是与主串s和索引i无关的，为了简化问题，我们只从模式串中讨论k和j的关系

tj与tk进行比较有两种情况

1.tj = tk的情况，则有以下关系，这种关系说明

由此可以推导，如果t串中的索引为j+1匹配发生错误，则可以比较k+1位置，因为t0-tk是与tj-k和tj是相等的，由定义，也就是说

 2.tj ≠ tk的情况

我们将tj的该部分看成主串，将tk的串看成模式匹配串，如果si与tj发生不匹配，我们想到si应该与tnext[j]位置进行比较，这两种情况是类似的。类似的思想，tj应该与t中索引为next[k]的字符进行比较，直到为-1或者匹配成功进行下一个字符的比较为止。

如果再次比较发现tk*与tj还是不等，继续按照上面的做法递归。

因此关于next的计算可由下述关系表示
 

由于next数组，是模式串自身的属性，因此在算法中只需要计算一次模式串的next数组就行

5)代码实现

求next数组的代码

  1. //计算next函数，简短版本(抄书的嘿嘿,写的确实妙)
  2. void get_next(const char* str, int next[], int len)
  3. {
  4. 	next[0] = -1; //-1表示ti+1指针和t0指针进行比较
  5. 	int i = 0, k = next[0]; //k是递归指针，从左往右，计算tk的值
  6. 	while (i-1 < len)
  7. 	{
  8. 		if (str[i] == str[k] || k == -1) //如果tk == ti，说明next[i+1] = k+1，当i+1指针不匹配时，应该匹配第k+1个位置 或者 当k为-1时，ti+1应该与t0比较
  9. 		{
  10. 			i++;
  11. 			k++;
  12. 			next[i] = k; //第i位置应该与k尾指针应比较  因为ti-1和tk-1相等,所以next[i] = k，当第i位置出错时，应该与第k位置比较
  13. 		}
  14. 		else
  15. 			k = next[k]; //当出现不匹配时，应继续比较上一个位置，因为next[k]，前面必定相等
  16. 	}
  17. }
  18.  
  19.  
  20. //易懂版本(自己写的，挫)
  21. void GetNext(const char* str, int next[],int len)
  22. {
  23. 	next[0] = -1; //-1表示模式匹配时，t0和si+1进行比较
  24. 	if (len == 1) //如果长度为1，直接退出
  25. 		return;
  26. 	next[1] = 0; //0表示当si字符和t1比较出现问题时，si应该与t0进行比较
  27. 	for (int i = 2; i < len; i++)
  28. 	{
  29. 		//i是不变的，j是变化的，j = next[j] 比较ti和tj的值，直到j = -1 就取消比较
  30. 		//计算next函数，如果tk和ti相等，则next[i+1] = next[i]+1
  31. 		//如果不相等，则另k = next[k]，继续比较tk和ti，如果相等则next[i+1] = next[k]+1
  32. 		//如果还不相等，则继续另k = next[k]，继续比较tk和ti的值，直到
  33. 		int k = next[i-1];
  34. 		while (k != -1) //如果k不等于-1，则一直比较
  35. 		{
  36. 			if (str[j] == str[i-1]) // 如果tk和tj相等，则说明应该与该点匹配
  37. 			{
  38. 				next[i] = k + 1;
  39. 				break;
  40. 			}
  41. 			else
  42. 				k = next[k];
  43. 		}
  44. 		if (k == -1)
  45. 			next[i] = 0;
  46. 	}
  47. }

KMP算法代码(优化版的BF算法，不改变i指针，j用next数组改善)

  1. #include <stdlib.h>
  2. #include <stdio.h>
  3. #include <string.h>
  4.  
  5. //KMP算法的实现，简短版本
  6. char* strfind_KMP(const char* str, const char* find)
  7. {
  8. 	int slen = strlen(str);
  9. 	int flen = strlen(find);
  10. 	int* find_next = (int*)malloc(sizeof(int) * flen);
  11. 	get_next(find, find_next, flen);
  12. 	int i = 0, j = 0; //i指针是指向主字符串，j指针是指向查找的字符串
  13. 	while (i < slen && j < flen) //如果i和j指针未查找到find中
  14. 	{
  15. 		if (j == -1 || str[i] == find[j]) //如果j为-1或str[i]和find[j]相等，则比较下一个位置
  16. 		{
  17. 			i++;
  18. 			j++;
  19. 		}
  20. 		else
  21. 			j = find_next[j];
  22. 	}
  23. 	return (j == flen) ? str + i-j:NULL; //如果比较完了，说明j和flen相同，返回指针，否则返回NULL
  24. }
  25.  
  26.  
  27. //KMP算法,易懂版本
  28. char* strfind_KMP2(const char* str, char* findstr) 
  29. {
  30. 	int len = my_strlen(str);
  31. 	int* str_next = (int*)malloc(len * sizeof(int));
  32. 	GetNext(str, str_next, len); //计算str的next数组
  33. 	int j = 0; //遍历findstr的指针
  34. 	char* ret = NULL; //记住字符串相等的开始位置
  35. 	while (*str && findstr[j]) //如果*str和*findstr其中有一个到了结尾，循环结束
  36. 	{
  37. 		if (*str == findstr[j]) //如果相等，则指针前进
  38. 		{
  39. 			if (j == 0)
  40. 				ret = str;
  41. 			str++;
  42. 			j++;
  43. 		}
  44. 		else //如果不相等，则比较下一个比较的位置
  45. 		{
  46. 			j = str_next[j];
  47. 			if (j == -1) //如果j为-1，则i指针和j指针都移动到下一个位置进行比较
  48. 			{
  49. 				j = 0;
  50. 				str++;
  51. 			}
  52. 		}
  53. 	}
  54. 	return findstr[j] == '\0' ? ret : NULL;
  55. }

4.KMP算法的时间复杂度推导

KMP算法的时间复杂度为O(m+n)，而BF算法为O(m*n)，由此可见，KMP算法在最坏情况下大大节约了比较时间。一次KMP算法包括计算next数组和主串与模式串匹配的时间。因此讨论KMP算法，要从next数组计算和主串与模式串匹配的两个角度进行分析。

1）next数组最坏情况

要让next数组时间复杂度变高，就是要让tj和tk的比较变多

如果模式串都是不等的字符，则这种next数组计算最快，只计算了n次，就计算出了next数组

索引j012345
模式串tabcdef
next[j]-100000

模式串如果有相等的字符，且没有规律，next数组计算不是最复杂的情况，但时间复杂度可能会大一点，范围是[n,2n)

索引j012345
模式串tabadef
next[j]-101100

模式串如果有相等的字符，有循环的规律，假设模式串有N个字符，T个字符一个周期

T为1，比较了6次

索引j012345
模式串taaaaaa
next[j]-101234

T为2，比较了6次

索引j012345
模式串tababab
next[j]-100123

 T为3，比较了6次

索引j012345
模式串tabcabc
next[j]-100012

 由以上情况可以预测到，当第一个周期除了第一个元素为-1外，其他都是0，后面的周期就是顺延0,1,2,3... 因此这种情况也不是最坏的情况

如果我们要让比较次数变多，next值必须尽可能的不为0，而且有一定的顺序且逐个变大，尽可能的比较多的元素，因此模式串的前面是循环的字符，而末尾是不等的字符，例如aaaaab，这种情况复杂度是最高的

比较了10次

索引j012345
模式串taaaaab
next[j]-101230

 假设有N个字符的情况，前N-1个字符都是一个字符，最后一个字符不同，则时间消耗为(2*N-2),因此计算next数组的时间复杂度为O(2*N-2) = O(N)

可见，像aaaaaaab的这种next数组计算，复杂度是最高的。

2）主串数组匹配的最坏情况

如果要让匹配复杂度变高，就需要多遍历比较模式串的字符，因为匹配时，比较失败，i指针不会回溯，j指针会回溯，让j指针回溯多次，就可以让复杂度变高，因此与模式串的next数组有很大的关系。

 如果si与tj匹配发生错误，i指针并不会回溯，影响匹配速度的，是j指针回溯的次数，回溯多，比较就慢，时间就变得复杂。因此像模式串aaaa的匹配主串aaabaaabaaab这种情况复杂度很高

索引j0123
模式串taaaa
next[j]-1012

 假设模式串长度为N，主串长度为M，M是N的整数倍，像上述情况，时间复杂计算如下

 但是这种情况复杂度不是最高的，而是像匹配串aaaab和主串aaaacaaaac的匹配，这种情况是最坏的

在上述情况的讨论可以看出，最复杂的情况如主串为aaacaaac，匹配串为aaab的这种情况，时间复杂度为O(M+N),而且无论是最坏的情况，时间消耗也没用2次项，时间复杂度低。在串匹配过程中，M往往远大于N，主串的长度远大于匹配串的长度，增加的时间也是值得的。

 5.KMP算法的优化

对于传统的KMP算法，如果是si和tj匹配发生了错误，在确定j的下一个位置时，只比较了tj-1和tk-1的位置，并没有比较tj和tk的位置，这是传统KMP算法的不足。比较这两个位置的意义是如果匹配发生错误，说明tj和si是不等的，如果tk和tj相等，则也没有比较的必要，再跳转到下一个，可以节省时间，因此对KMP算法的优化，只是优化了next数组的计算

 例如计算模式串aaaaa的next数组时

传统的KMP算法的next数组

索引j012345
模式串taaaaaa
next[j]-101234

 如果在比较的时候，si与t5并不匹配，说明si是不等于t5的，是不等于a的，如果比较a，肯定也是不匹配的，传统的KMP算法并没有注意到这一点（但是还是要说KMP算法思想太强了），因此在计算next数组的时候，也需要判断tj和tk是否相等，如果不等，k就是j的下一个比较的位置，如果相等，则继续跳转到k的下一个位置。

优化的KMP算法的next数组

索引j012345
模式串taaaaaa
next[j]-100000

代码实现

  1. //简单版本
  2. //原版的next数组，只是比较了前k-1个位置，但是tj和tk并没有比较，这是原next的不足之处。如果tj和tk仍然相等，则没有比较的必要，继续下一个位置，直到满足条件
  3. void get_new_next(const char* str, int newnext[], int len)
  4. {
  5. 	newnext[0] = -1;
  6. 	int i = 0, j = -1; 
  7. 	while (i < len - 1)
  8. 	{
  9. 		if (j == -1 || str[i] == str[j])
  10. 		{
  11. 			j++; //更新j指针
  12. 			i++; //更新i指针
  13. 			if (str[i] != str[j]) //如果ti和tj不相等，说明就是该位置
  14. 				newnext[i] = j;
  15. 			else  //如果不等，则是下一个位置，因为递归的时候，前面不可能相等，所以直接取下一个位
  16. 				newnext[i] = newnext[j];
  17. 		}
  18. 		else
  19. 			j = newnext[j];
  20. 	}
  21. }
  22.  
  23. //易懂版本
  24. void GetNewNext(const char* str, int next[], int len)
  25. {
  26. 	next[0] = -1;
  27. 	if (len == 1) //如果匹配字符串长度只有1，则直接返回
  28. 		return;
  29. 	next[1] = 0;
  30. 	for (int i = 2; i < len; i++) //计算i的next值
  31. 	{
  32. 		int k = next[i - 1];
  33. 		while (k != -1) //如果j为-1，则结束循环
  34. 		{
  35. 			if (str[i - 1] == str[k] && str[i] != str[k]) //比较ti+1和tk字符是否相等，并且判断ti和tk是否相等，如果不相等，则就是下一个
  36. 			{
  37. 				next[i] = k + 1;
  38. 				break;
  39. 			}
  40. 			else
  41. 				k = next[k];
  42. 		}
  43. 		if (k == -1)
  44. 			next[i] = 0;
  45. 	}
  46. }

  6.学习KMP算法的感受

要理解KMP算法的思想，确实花了不少时间...而且要清KMP算法的时间复杂度，真的是一件很抽象的事情。。。这个KMP算法的解是个递归的想法，递归确实让问题简单了很多，这正是伟人的伟大之处。我相信对于模式匹配算法来说，BF算法的改进之前肯定也有很多人和KMP的思想相似，但递归和问题的提炼能力，对于问题的深度挖掘，不断突破，这正是他们的伟大。可以尝试用递归的思想去解决难的问题，总结条件，找出问题所在。

虽然学习算法难，但是我们一直都乐此不疲，悟出来那个瞬间，让人顿时开心，如果喜欢数学偏多的硬核解读，可以三连支持我一下，总结不易，谢谢支持~~~~ 

声明：本文内容由网友自发贡献，不代表【wpsshop博客】立场，版权归原作者所有，本站不承担相应法律责任。如您发现有侵权的内容，请联系我们。转载请注明出处：https://www.wpsshop.cn/w/很楠不爱3/article/detail/583228
推荐阅读
相关标签

Copyright © 2003-2013 www.wpsshop.cn 版权所有，并保留所有权利。

  

闽ICP备14008679号