写在前面

在学习KMP算法前,不才也曾在众多博客中阅读过KMP算法的文章,但是都看得迷迷糊糊,所以不才在学透了KMP算法后,详细编写了这篇笔记,希望对你有帮助。

KMP算法的核心思想不分任何语言,但是不才在实现代码中时使用C语言实现。


一、什么是KMP算法

在学KMP算法前,我们首先需要知道KMP算法是什么,干什么用的(你滴什么滴干活🫡)。

KMP算法是:查找源字符串在目标字符串中出现的位置。并返回一个指向str1中str2第一次出现的指针,如果str2不是str1的一部分,则返回一个空指针。实际上就是与(strstr)相似,但是strstr是使用BF算法(暴力算法)进行查找的。

本篇笔记需要有BF算法的基础,这里可以参考不才写的字符函数和字符串函数笔记

模拟实现的strstr:【C语言】字符函数和字符串函数icon-default.png?t=O83Ahttps://blog.csdn.net/m0_71580879/article/details/142614046


二、为什么要使用KMP算法

假设我们str1的数组有n个元素str2的数组有m个元素。我们使用BF算法的时间复杂度就是O(n*m),如果是两数组个巨无霸的的情况,我们使用的BF算法就非常耗时。但是使用KMP算法我们就可以把时间复杂度变为:O(n+m)。若m与n相同的情况下:BF算法的时间复杂度O(n^2)、KMP算法时间复杂度为O(n)。这样我们的时间成本就大幅度下降。

三、KMP算法的核心思想

利用匹配失败后的信息,尽量减少模式串与主串的匹配次 数以达到快速匹配的目的。具体实现就是通过一个next()函数实现, 函数本身包含了模式串的局部匹配信息。KMP算 法的 时间复杂度O(m+n)

上文是一个压缩后很正确的表诉方式,但是为了更好理解上面这段话,不才在下面进行逻辑上的表诉。

假设我们主串str1的数组有n个元素,子串str2的数组有m个元素

KMP算法为了达到时间复杂度为:O(n+m)。那我们就需要遍历str1数组的指针不返回为了实现遍历str1数组的指针不返回,我们就需要创建一个数组next数组保存我们str2数组中如果出现错误我们需要str2数组回退的位置

而怎么计算next数组中的值就是我们KMP算法的核心逻辑了。


四、证明遍历主串str1数组的指针可以不返回

首先,我们先举例说明一下,为什么遍历主串str1数组的指针可以不返回。

例子一:

在上图中,我们使用BF算法比较的话,我们在str1和str2比较之前我们肯定需要一个dst1和一个dst2来定位比较前的位置的(如下图):我们先肉眼观察

当我们 i j 比较到下标为2时候,发现不匹配,那么我们的dst1就会+1指向b字符处。但是我们知道的是,str1[0] == str2[0]、str1[1] == str2[1]、str1[0] != str1[1] 可得str1[1] != str2[0] ,那么我们的dst1+1指向b字符处的比较大可不必的,我们dst可以直接在 i 处继续进行比较。这样就达成了我们遍历主串str1数组的指针可以不返回。

当然有朋友就回提出质疑了,就一个特殊案例可以说明了?你 j 怎么移动?啊?

别急 接着往下看


例子二: 

此时我们又有一个案例:

开始比较后,下标走到5后,出现了不匹配的情况:

在此时,我们没有出现元素各不相等的情况。

出现了:

  • str1[0]…str1[1] == str2[0]…str2[1] (ab == ab)
  • str1[3]…str1[4] ==  str2[0]…str2[1](ab == ab)

我们继续使用BF算法来理解,根据上面例一的推理,我们可以得出dst1需要加到下标为3处开始比较才有意义。但是上面的推理 str1[3]…str1[4] ==  str2[0]…str2[1] 可以看出,我们下标3、4都是相等的,那么我们的dst1又可以不进行回退了,保持在 i 的位置,我们只需要 j 下标退回下标2处开始比较即可。如下图:

那此时我们应该怎么知道我们指针 j 应该回退到哪个下标处呢?

 我们就需要创建一个数组next数组保存我们str2数组中如果出现错误我们需要 j 回退的位置


 五、next数组

KMP 的精髓就是 next 数组:也就是用 next[j] = k;来表示,目前 j 代表的是next数组的下标不同的 j 来对应一个 K 值, 这个 K 就是你将来要移动的 j 要移动的位置

5.1肉眼手搓next数组

手搓next数组即手搓K值,在此之前我们需要知道手搓K值规则是什么:

  1. 找到匹配成功部分的两个相等的真子串(不包含本身),一个以下标 0 字符开始,另一个以 j-1 下标 字符结尾。匹配成功那么 字串的长度 就等于 k值。
  2. 不管什么数据 next[0] = -1;next[1] = 0;在这里,我们以下标来开始,而说到的第几个第几个是从 1 开始;

我们使用第四小节的例子二为栗子:

手搓K值:

  • 上来不管三七二十一先把: next[0] = -1 next[1] = 0
  • next[2]下标为 2 时str2[0]:a 与 str2[j - 1] 即 str2[2 - 1] ==> str2[1]:b。那么就找以 a 开始b结尾两个连续相等的字串。明显没有~,那么 next[2] = 0;
  • next[3]下标为 3 时:找以 a 开始c结尾两个连续相等的字串。只有本身(abc一个字串),那k值为0,那么 next[3] = 0;
  • next[4]下标为 4 时:找以 a 开始a结尾两个连续相等的字串。a开头a结尾,那a就有两个字串呀( str2[0]...str2[0] == str2[3]...str2[3] ),那么k就为1,即 next[4] = 1;(下图)

  • next[5]下标为 5 时:找以 a 开始b结尾两个连续相等的字串。a开头a结尾,那ab就有两个字串呀( str2[0]...str2[1] == str2[3]...str2[4] ),那么k就为 2,即 next[5] = 2;(下图)

由上面手搓可以得出:next数组为:next[5] = {-1, 0, 0, 0, 1, 2};对应着str2的 j 指针在哪个位置出错就返回next对应的位置

譬如:

  • j下标为5时比较错误。返回值为:next[5]
  • j下标为 2 时比较错误。返回值为:next[2]

 手搓K值我们理解了如何手搓,那么在程序中,代码根本就不会想我们人眼一样肉眼手搓出来,我们要怎么计算出K值呢?

5.2计算K值

重要结论:

  1. str[i - 1] == str[K](K == next[i-1]),我们可以直接把next数组的i下标赋值为 K+1。即:next[ i ] = k + 1;
  2. str[i - 1] != str[K](K == next[i-1]),我们需要K值移动到str[K]处的K值,即K = next[K],在K值重新赋值定位后,我们再把str[i - 1] 与 str[K]进行比较直到               str[i - 1] == str[K]。或K为-1
  3. str[i - 1] != str[K]时,我们循环比较没有成功str[i - 1] == str[K]。那K一定会为-1,在K为-1时已经没有所对应匹配的字符了,所以直接把下标 i 处的next数组值赋值为:0。即next[i] = 0

我们使用逻辑推理:在5.1例子中 next数组为:next[5] = {-1, 0, 0, 0, 1, 2};

此时我们定义一个变量 int i = 0;

若i = 4时, 那next数组中有:str2[0]...str2[0] == str2[3]...str2[3],即next[4] = 1;

此时,我们把变量名称代入可以得到一个表达式:str2[0]...str2[0] == str2[3]...str2[3] ==> str2[0]...str2[?] == str2[?]...str2[i - 1]

且:k = next[i] ;  (i = 4, k = 1),即可得到下图:

计算问好:

  • 问好一:我们知道是由下标0到0拼接成第一个字串,即第一个字串a。在上图中我们可以看到第一个问好就是: k - 1 即:str2[0]...str2[k - 1] == str2[?]...str2[i - 1]
  • 问好二:我们知道是由下标 3 到 3 拼接成第二个字串,即为第二个字串a。那第二个问好为: x。此时,x是未知的,但是我们知道:str2[0]...str2[k - 1] == str2[x]...str2[i - 1]绝对成立

因为长度是一定相等的,那么可以推出k-1 - 0 == i-1 - x。是恒成立的。

k-1 - 0 == i-1 - x  =>  k-1 = i-1 - x  =>  x = i-1 - k+1  即   x = i - k

我们就得出求 k 值重要公式str2[0]...str2[k - 1] == str2[i - k]...str2[i - 1] 

如果此时我们假设不知下标为 5 的k值,求i = 5时K值为多少

当 i= 5 时,我们观察上图可以发现,str2[i - 1] == str2[K](此时的 K 值时对应着 i - 1 的K值,K=1)。

str2[4] == str2[1],在str2[i - 1] == str2[K]相等的情况下(使用重要结论1),我们把 i 值代入得:str2[i - 1] == str2[K]下标为5 next数组的k值是 i - 1 下标的k值加1。即:next[5] = 2

总结:我们虽然是举了个特例证明,当str2[i - 1] = str2[K]时,next[i] = K + 1。(此时的 K 值时对应着 i - 1 的K值)。

我们举个栗子二来说明,当 str2[i - 1] != str2[K]应该怎么操作

例子二:

 在上面数组中,我们使用计算的方法把next数组计算出来。

  • 首先不管三七二十一,next[0] = -1 与 next[1] = 0,先录入数组
  • 此时我们就遇到str1[i - 1] != str1[K]的情况。

str1[i - 1] != str1[K]时,我们只需要把 K 移动到当前str1[K]所对应的next数组K值即可,即把此时的str[K]的 next[1] 赋值个 K,即为:K = next[K],那么K就移动到了下标0处。(如下图)

那此时再继续判断str1[i - 1]是否str1[K]相等。此时我们还是不相等,那K继续移动K = next[K]。但是此时next[K]等于 -1 ,已经没有所对应匹配的字符了,所以直接把下标为2处的next数组值赋值为:0

那此时我们i下标继续向后移动,K值重新赋值到next[i - 1]处(此时next[2] = 0)。再来判断str1[i - 1]是否与str1[K]相等

此时:str1[i - 1] 等于 cstr1[K]等于a,此时又回到了我们str1[i - 1] != str1[K]的情况,那么我们继续把 K 移动当前str1[K]所对应的next数组K值,继续比较,但是此时next[K]等于 -1 ,已经没有所对应匹配的字符了,所以直接把下标为3处的next数组值赋值为:0。即next[i] = 0。如下图

那此时我们i下标继续向后移动,K值重新赋值到next[i - 1]处(此时next[3] = 0)。再来判断str1[i - 1]是否与str1[K]相等

此时:str1[i - 1] 等于 a,str1[K]也等于a,那就回到了我们 str1[i - 1] == str1[K] 相等的时候,那此时我们next的表达式就为:next[i] = K+1,即next[4] = 0+1 => next[4] = 1。可得下图

那此时我们i下标继续向后移动,K值重新赋值到next[i - 1]处(此时next[4] = 1)。再来判断str1[i - 1]是否与str1[K]相等

此时:str1[i - 1] 等于 b,str1[K]也等于b,那就回到了我们 str1[i - 1] = str1[K] 相等的时候,那此时我们next的表达式就为:next[i] = K+1,即next[5] = 1+1 => next[5] = 2。可得下图

以上面逻辑继续我们最终就可以得到next数组的全部内容:

至此,我们KMP算法的next数组求值方法我们就全部掌握了。

5.3总结

我们要实现KMP算法的时间复杂度可以达到O(m+n),我们就得确保主串的遍历指针 j 不回退,为了主串的遍历指针i不回退,我们就要字串的遍历数组 i 配合i 需要回退到特定位置,而next数组就是存放字串 i 再当前下标比较失败后需要回退的位置

在next中,我们需要计算出每一个下标对应的K值,而K值的计算正时KMP算法的难点,我们需要分类讨论

  • str[i - 1] == str[K](K == next[i-1]),我们可以直接把next数组的i下标赋值为 K+1。即:next[ i ] = k + 1;
  • str[i - 1] != str[K](K == next[i-1]),我们需要K值移动到str[K]处的K值,即K = next[K],在K值重新赋值定位后,我们再把str[i - 1] 与 str[K]进行比较直到               str[i - 1] == str[K]。或K为-1

  • str[i - 1] != str[K]时,我们循环比较没有成功str[i - 1] == str[K]。那K一定会为-1,在K为-1时已经没有所对应匹配的字符了,所以直接把下标 i 处的next数组值赋值为:0。即next[i] = 0

六、思想转换代码

#define _CRT_SECURE_NO_WARNINGS 1
#include <stdio.h>
#include <assert.h>
#include <string.h>
#include <stdlib.h>

void my_next(const char* str2, int* next) {
	assert(str2 && next);
	next[0] = -1;
	next[1] = 0;
	int i = 2;//str数组只需要从下标为2处开始比较,因为下标0、1的next数组都是默认值
	int K = next[i - 1];
	while (str2[i]) {//判断当前str数组是否为结束符标志'\0'
		
		if (str2[i - 1] == str2[K] || K == -1) {//判断str2的i-1处的值是否与K处的值相等 ,或者K等于-1时进来改变赋值
			next[i] = K + 1;
			i++;
			K = next[i - 1];
		}
		else {
			K = next[K];
		}
	}
}

char* my_KMP(const char* str1,char* str2) {
	assert(str1 && str2);
	int len1 = strlen(str1);
	int len2 = strlen(str2);
	int* next = (int* )malloc(len2 * sizeof(int));
	if (next == NULL) {
		perror("my_KMP的next开辟空间:>");
		return;
	}
	my_next(str2, next);//创建好next数组
	int i = 0;
	int j = 0;
	while (i < len1) {
		if (str1[i] == str2[j] || j == -1) {
			i++;
			j++;
		}
		else{
			j = next[j];
		}
		if (j == len2) {
			return str1 + i - j;
		}
	}
	free(next);
	next = NULL;
	return NULL;
}

int main() {
	char arr1[] = "1233321123";
	char arr2[] = "33";
	char* ptr = my_KMP(arr1, arr2);
	printf("%s", ptr);

	return 0;
}
  • 我们先从main函数开始,我们需要实现一个KMP嘛。我们创建一个KMP函数命名为:my_KMP函数
  • my_KMP函数中我们先创建next数组,在创建next数组后,我们就需要把字串的K值全部计算并赋值到next数组中,这时我们就创建一个my_next函数用来计算字串的K值
  • 在my_next数组中,我们使用 5.3总结知识转换成代码,来实现存储K值到对应的next数组中。在一上来我们肯定不管三七二十一就先把next数组的0、1下标赋值为:next[0] = -1;
    next[1] = 0;
    之后我们就把 5.3总结实现。
  • 在存储好了next数组后,我们就实现比较逻辑,在比较中,我们是需要主串的 i 不返回i 值就只能在 匹配成功 字串的下标为 -1时 才能后移。在匹配不成功时,我们就需要 i 下标不移动j 移动到next数组对应的值中,继续比较,在j == len2时说明比较成功,就返回str1数组的对应地址。
  • 对应地址的计算: 主串移动的下标 i 减 字串的下标 j 就得到主串匹配成功的起始位置,str1 加上 匹配成功的起始位置 就可以得到 具体的地址。

以上就是本章所有内容。若有勘误请私信不才。万分感激 若有帮助不要吝啬点赞哟~~

ps:表情包来自网络,侵删

若是看了这篇笔记彻底拿捏KMP算法的就可以在评论区打出:小小KMP!拿捏!

点赞(0) 打赏

评论列表 共有 0 条评论

暂无评论

微信公众账号

微信扫一扫加关注

发表
评论
返回
顶部