【算法】KMP算法

embedded/2024/10/22 1:30:32/

写在前面

在学习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] 等于 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 加上 匹配成功的起始位置 就可以得到 具体的地址。

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

ps:表情包来自网络，侵删🌹

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


http://www.ppmy.cn/embedded/129424.html

相关文章

Qt与下位机通信时，如何等待下位机回复和超时处理

Qt与下位机通信时，如何等待下位机回复和超时处理

在C或Qt中实现与下位机&#xff08;例如嵌入式设备、传感器等&#xff09;的通信&#xff0c;并且需要等待对方回复&#xff0c;如果几秒后没有收到回复则执行下一步动作&#xff0c;可以使用多种方法来实现这种超时机制。以下是几种常见的实现方式&#xff1a; 1. 使用 QTime…
阅读更多...
统一修改UI库样式的几种方式

统一修改UI库样式的几种方式

统一修改element组件库样式的几种方式。主题 | Element Plus 通过css变量设置 【CSS扩展】VUE如何使用或修改element plus中自带的CSS全局变量来定义样式:root {--hc-text-color-placeholder: #5f84a2;--hc-text-color-regular: #fff;--hc-text-color-primary: #fff;--hc-bg-c…
阅读更多...
Vite：功能

Vite：功能

一、前言 对非常基础的使用来说&#xff0c;使用 Vite 开发和使用一个静态文件服务器并没有太大区别。然而&#xff0c;Vite 还通过原生 ESM 导入提供了许多主要用于打包场景的增强功能。 二、NPM 依赖解析和预构建# 原生 ES 导入不支持下面这样的裸模块导入&#xff1a; impor…
阅读更多...
04，perl

04，perl

1 &#xff0c;作用 &#xff1a; 2 &#xff0c;原理 &#xff1a; 3 &#xff0c;使用场景 &#xff1a;
阅读更多...
HTML快速入门--第二节--css选择器

HTML快速入门--第二节--css选择器

一、基本概念 CSS:层叠样式表 样式&#xff1a;外观属性 层叠&#xff1a;一个标签对象&#xff0c;最终呈现出来的样子&#xff0c;多个样式共同作用 表&#xff1a;.css后缀文件 tr是列 td是行 div :能整齐装东西 空格td :后代 >td:子代 选择…
阅读更多...
Unity中面试遇到的问题--C#--dynamic

Unity中面试遇到的问题--C#--dynamic

C#中的Dynamic相关的知识点 在C#中&#xff0c;dynamic 关键字允许我们延迟对对象类型的解析。这意味着我们可以声明一个变量为 dynamic 类型&#xff0c;而不需要知道它的确切类型。在编译时&#xff0c;编译器不会检查 dynamic 变量的类型&#xff0c;而是将类型检查推迟到运…
阅读更多...
演示：基于WPF的DrawingVisual开发的高刷新率示波器

演示：基于WPF的DrawingVisual开发的高刷新率示波器

一、目的&#xff1a;分享一个基于WPF的DrawingVisual开发的高刷新率示波器 二、效果演示 特此说明&#xff1a;由于Gif录制工具帧率不够&#xff0c;渲染60帧用了4.6秒&#xff0c;平均帧率在12Hz左右&#xff0c;所以展示效果不好&#xff0c;想要看好些的效果可以看文章下面…
阅读更多...
Android Studio Ladybug指定ndk版本

Android Studio Ladybug指定ndk版本

背景 想指定项目的ndk版本。 遇到错误 之前版本在gradle中配置ndk版本是这样的 ndkVersion "26.0.10792818"到了最新版as的时候提示错误&#xff0c;这个语法不存在了。 真的想骂人&#xff0c;这个as天天改语法&#xff0c;吃饱了没事做是吧。 android {namesp…
阅读更多...
最新文章

Copyright @ 2022~2023