【算法】KMP算法

写在前面

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

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

一、什么是KMP算法

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

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

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

中模拟实现的strstr：【C语言】字符函数和字符串函数https://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值的规则是什么：

找到匹配成功部分的两个相等的真子串（不包含本身），一个以下标 0 字符开始，另一个以 j-1 下标字符结尾。匹配成功那么字串的长度就等于 k值。
不管什么数据 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值

重要结论：

当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

我们使用逻辑推理：在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] 等于 c，str1[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 加上匹配成功的起始位置就可以得到具体的地址。