KMP算法
🌏个人博客主页：心.c
前言： 前段时间练习了算法，深入了解了KMP算法思维，今天和大家分享一下如何通过KMP更好地完成字符串对子字符串的查找！
🔥🔥🔥文章专题：KMP
😽感谢大家的点赞👍收藏⭐️评论✍您的一键三连是我更新的动力 💓
目录
如果给你一道这样的算法题（你该如何给更好的处理解决呢？） ：
两个字符串
haystack和needle，请你在haystack字符串中找出needle字符串的第一个匹配项的下标（下标从 0 开始）。如果needle不是haystack的一部分，则返回-1。示例 1：
输入：haystack = "sadbutsad", needle = "sad" 输出：0 解释："sad" 在下标 0 和 6 处匹配。 第一个匹配项的下标是 0 ，所以返回 0 。
当我们看到这种算法题时，我们的第一反应可能是进行两次for循环进行遍历，虽然这样也可以将代码进行提交，但是它的空间复杂度为O(n * m) ，我们的主串很长时，这种for循环就会产生很大的弊端，在运行上花费很多时间，这种for循环不会灵活变通，不太友好，所以这样解决不是一个好的算法思维的解决方法，我们应该通过其他知识来进行更加灵活的求解，下面我将会跟大家分享KMP，一种高效的字符串匹配算法
KMP理论讲解：
内容：
KMP算法是一种高效的字符串匹配算法，用于在一个较长的文本字符串中查找一个较短的模式字符串。KMP 算法的主要优点是它可以在 O(n + m) 的时间内完成搜索，其中 n 是文本字符串的长度，m 是模式字符串的长度。
通过上面KMP算法的适用我们就可以明白，KMP算法是当前解决主字符串中查找子字符串最方便的一种算法思维，所以今天我们通过学习KMP来解决我们写相关类型算法的面临的问题
复杂度：
KMP 算法的时间复杂度为 O(n + m)，空间复杂度为 O(m)。
- 时间复杂度 (Time Complexity): 描述算法运行所需时间的增长率，通常表示为输入规模（如数组长度、字符串长度等）的函数。它关注的是随着输入规模增长，算法执行时间的增长趋势。
- 空间复杂度 (Space Complexity): 描述算法运行所需的额外内存空间的增长率，通常也是表示为输入规模的函数。它关注的是随着输入规模增长，额外内存使用的增长趋势。
核心：
在于构建一个next 数组的数据结构。这个表用于记录模式字符串的前缀与其最长相等前后缀的长度。有了这个表，KMP 算法可以避免在匹配过程中重复比较已经比较过的字符，从而提高了效率。
要想创建next数组，首先我们先了解一下关于前缀和后缀的一些概念，因为这里的next数组要记录的是子字符串的前缀与其最长相等前后缀的长度，next数组中记录是的关于子串的前缀的前缀和后缀的最长相等长度
前缀和后缀的概念：
前缀和后缀不加后面的一个字符或者前面的一个字符，也就是上面字符串中的前缀不包括C，后缀不包括A
虽然C没有加入前缀，但是我们在这里默认为0
所以next的数组在这个子字符串中就赋值就为{0，0，1，2，0}
下面我们将通过这组字符串来进行讲解：
（下面这三张照片很抱歉，视频上传不了，所以只能把比较重点的图片拿出来给大家看了，大家不要见怪）
- 定义一个n,m（提示n的值只会增不会减）
- 起始n=m=0
- 如果主串下标n的值等于子串下标m的值 n和m都加一，将下标同时向前移动一位
- 下图1为n=m=3时刻，因为前面值都相等
- 下图2为n=m=4时刻，但是主串下标n的值不等于子串下标m的值，所以n和m要发生变化
- 下图3为n=4,m=2,因为我们判断当主串下标n的值不等于子串下标m的值时，n值不变，然后让m返回m-next[m-1]（只要主串下标n的值不等于子串下标m的值就可以一直这样循环），这样n可以不进行返回，只有m移动，大大减少了不必要的循环遍历（这里的理解非常非常重要）
- 然后后面的步骤就是和上面的一样直到找到子字符串或者n达到最大值
图一
图二
图三
想必大家看到这里已经对KMP有些理解了，下面我们通过代码进行实践
KMP算法讲解：
相关KMP算法：
2.力扣-最短回文串
下面我将和大家分享一下上面提及的那一道算法题，我使用的是KMP来进行解决的(我是c++语言写的，大家可以了解一下我的思路然后直接上路，通过我上面的分析和对代码的理解可以自己解决这个KMP算法.
next数组的创建：
首先通过子字符串来创建next数组
// 通过KMP来创建next数组
vector<int> getNext(const string& needle) {
vector<int> next;
next.push_back(0); //数组的第一个值都是0，所以直接进行赋值
int index = 0;
int i = 1;
while (i < needle.length()) {
if (needle[index] == needle[i]) {
index++;
next.push_back(index);
i++;
} else if (index > 0) {
index = next[index - 1];
} else {
next.push_back(0);
i++;
}
}
return next;
}遍历数组找到子字符串：
int strStr(const string& haystack, const string& needle) {
vector<int> next = getNext(needle);
int hindex = 0;
int nindex = 0;
while (hindex < haystack.length() && nindex < needle.length()) {
if (haystack[hindex] == needle[nindex]) {
hindex++;
nindex++;
if (nindex == needle.length()) {
return hindex - nindex;
}
} else if (nindex > 0) {
nindex = next[nindex - 1];
} else {
hindex++;
}
}
return -1;
}总代码：
// 通过KMP来创建next数组
vector<int> getNext(const string& needle) {
vector<int> next;
next.push_back(0);
int index = 0;
int i = 1;
while (i < needle.length()) {
if (needle[index] == needle[i]) {
index++;
next.push_back(index);
i++;
} else if (index > 0) {
index = next[index - 1];
} else {
next.push_back(0);
i++;
}
}
return next;
}
int strStr(const string& haystack, const string& needle) {
vector<int> next = getNext(needle);
int hindex = 0;
int nindex = 0;
while (hindex < haystack.length() && nindex < needle.length()) {
if (haystack[hindex] == needle[nindex]) {
hindex++;
nindex++;
if (nindex == needle.length()) {
return hindex - nindex;
}
} else if (nindex > 0) {
nindex = next[nindex - 1];
} else {
hindex++;
}
}
return -1;
}到这里就结束了，不懂的可以给我私信哦
原文地址：https://blog.csdn.net/2301_81253185/article/details/140847776
免责声明：本站文章内容转载自网络资源，如本站内容侵犯了原著者的合法权益，可联系本站删除。更多内容请关注自学内容网（zxcms.com）！