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)!