代码随想录算法训练营DAY9|C++字符串Part.2|LeetCode:28.实现strStr()、459.重复的子字符串|KMP算法
文章目录
- 28.实现strStr()
- 思路
- CPP代码
- 459.重复的子字符串
- 思路
- 移动匹配
- KMP算法
- CPP代码
- 移动匹配
- KMP算法
28.实现strStr()
力扣题目链接
文章链接:28.实现strStr()
视频链接:
- 帮你把KMP算法学个通透!B站(理论篇)
- 帮你把KMP算法学个通透!(求next数组代码篇)
状态:KMP算法顶中顶,以后一定要搞熟搞透
关于KMP算法的理论基础,这里最推荐的是《大话数据结构》–程杰的讲解。听完卡哥视频之后,再看看这本书关于KMP算法的解释,立马就通透了。
思路
没啥别的,就是KMP算法最基础的应用。
-
构造next函数:定义一个函数
getNext
来构建next
数组,函数参数为指向next
数组的指针,和一个字符串。void getNext(int* next, const string& s)
- 初始化:定义两个指针
i
和j
。j
指向前缀末尾位置,同时j
还代表着包括i
之前的子串的最长相等前后缀的长度。i
指向后缀末尾位置
int j = 0; //我们的前缀肯定是从0 开始 next[0] = j; //i的初始化已经进入了循环遍历的过程.在循环中我们需要比较前缀和后缀所对应字符是否相等。所以i必须从1开始 for (i = 1; i < s.size(); i++){}
- 处理前后缀不相同的情况:之前我们说过,如果子串遇到不匹配的位置,应该看该位置的前一位,来看这个位置前缀表中对应的值,来回退到前缀表中对应值的数组下标;那么前缀末尾和后缀末尾不匹配的时候,就应该向前回退。其实遇到冲突看前一位就是我们的循环不变量。那么我们的
j
回退到0位置为止,也就是如果一直前后缀末尾不同,就一直回退到初始位置。
s[i] != s[j];//前缀末尾和后缀末尾不匹配的时候,就应该向前回退 j > 0; //`j`回退到0位置为止,也就是如果一直前后缀末尾不同,就一直回退到初始位置//综上,处理前后缀不相同的情况代码如下 while (j > 0; s[i] != s[j]){ //while表示一个连续回退的过程j = next[j-1];//回退,看它的前一位的next数组的值。 }
- 处理前后缀相同的情况:还记得之前说过:
j
指向前缀末尾位置,同时j
还代表着包括i
之前的子串的最长相等前后缀的长度。所以如果遇到了前后缀相等的情况,j
一定要做+1
的操作
if (s[i] == s[j]) j++;
- 更新next数组的值:之前说过,
j
指向前缀末尾位置,同时j
还代表着包括i
之前的子串的最长相等前后缀的长度。这里我们直接填入j
的值
//直接填入j的值即可。 next[i] = j;
- 初始化:定义两个指针
综上所述,更新完next的值之后,我们还要把i向前走一位,还记得我们是在for
循环中遍历的不?
void getNext(int* next, const string& s) {int j = 0;next[0] = 0;for(int i = 1; i < s.size(); i++) {while (j > 0 && s[i] != s[j]) { // j要保证大于0,因为下面有取j-1作为数组下标的操作j = next[j - 1]; // 注意这里,是要找前一位的对应的回退位置了}if (s[i] == s[j]) {j++;}next[i] = j;}
}
- 上述代码的模拟运行过程可以参考:帮你把KMP算法学个通透!(求next数组代码篇)中模拟运行过程部分。
CPP代码
class Solution {
public:void getNext(int* next, const string& s) {int j = 0;next[0] = 0;for(int i = 1; i < s.size(); i++) {while (j > 0 && s[i] != s[j]) {j = next[j - 1];}if (s[i] == s[j]) {j++;}next[i] = j;}}int strStr(string haystack, string needle) {if (needle.size() == 0) { //特殊情况处理return 0;}int next[needle.size()]; //定义next数组getNext(next, needle); //初始化next数组int j = 0;for (int i = 0; i < haystack.size(); i++) {while(j > 0 && haystack[i] != needle[j]) { //如果不匹配,进行会退j = next[j - 1];}if (haystack[i] == needle[j]) { //匹配上了继续遍历,j和i同时后移j++; //i的增加在for循环里}if (j == needle.size() ) { //文本串中出现了模式串return (i - needle.size() + 1);}}return -1;}
};
459.重复的子字符串
力扣题目链接
文章链接:459.重复的子字符串
视频链接:字符串这么玩,可有点难度! | LeetCode:459.重复的子字符串
状态:典型的字符串匹配的问题,最主要的难点就是我们如何拿到模式串即字符串的子串呢?
思路
移动匹配
抓到一个重点:任何由重复子串组成的字符串,它的前半部分和后半部分一定是相等的。
其实按照题目的说法,如果这个字符串可以由重复子串构成,那么它前半部分和后半部分肯定是想定的(不过不一定非得从中间劈开的相等)
那么如果这是个重复的字符串,那么我们从后面再重复加一遍,变成s+s
,那么这个字符串中也一定是包含了一个新的s
,比如s=abcabc,s+s = abc|abcabc|abc
,这里就出现了一个新s
。但是我们在拼接之后一定要删除首尾字母,以免搜索过程中搜到我们原来的s
和后来加的s
,如果这样还能找到一个s
,那么说明该字符串由重复子串组成。
假设t = s + s
;
那么有查找字符串中某个子串或字符位置的方法:
if (t.find(s) != std::string::npos)//如果不等于,意味着find方法成功找到了子串s在字符串t中的位置
在C++
中,std::string::npos
是一个常量,表示std::string
中某个操作(如查找)失败时的返回值。它实际上是std::string
类型的最大可能长度,通常被定义为-1
。由于std::string
的长度是使用无符号整数类型(如size_t
)表示的,-1
会被转换成无符号类型,结果是这个类型能表示的最大值。
当你使用std::string
的find
方法或其他可能查找字符串中某个子串或字符位置的方法时,如果查找失败(即未找到指定的子串或字符),方法会返回std::string::npos
。因此,通过检查方法的返回值是否等于std::string::npos
,你可以判断查找操作是否成功。
KMP算法
这里的KMP算法主要就是用来求最长相等前后缀。因为一个字符串的最长相等前后缀长度就是next[size - 1]。
因为一个由重复子串组成的字符串中,最长相等前后缀不包含的子串就是最小重复子串。
-
首先让我们复习一下前缀和后缀的概念:
- 前缀:前缀是指不包含最后一个字符的所有以第一个字符开头的连续子串;
- 后缀:后缀是指不包含第一个字符的所有以最后一个字符结尾的连续子串
-
如何找最小重复子串:
- 结论:由重复子串组成的字符串中,最长相等前后缀不包含的子串就是最小重复子串。
- 证明过程:建议直接去看视频-KMP解法-最小重复子串推导
-
综上,如何进行求解呢?
- 整个字符串长度len,最长相等前后缀是next[len - 1]
- 源字符串长度减去最长相等前后缀的长度,剩下的就是最长相等前后缀不包含的子串就是最小重复子串的长度。那么如果是重复子串的话,那么这个长度肯定可以被源字符串长度len整除:
len % (len - next[size-1]) == 0;
CPP代码
移动匹配
class Solution {
public:bool repeatedSubstringPattern(string s) {string t = s + s;t.erase(t.begin()); t.erase(t.end() - 1); // 掐头去尾if (t.find(s) != std::string::npos) return true; // rreturn false;}
};
KMP算法
class Solution {
public:void getNext (int* next, const string& s){next[0] = 0;int j = 0;for(int i = 1;i < s.size(); i++){while(j > 0 && s[i] != s[j]) {j = next[j - 1];}if(s[i] == s[j]) {j++;}next[i] = j;}}bool repeatedSubstringPattern (string s) {if (s.size() == 0) {return false;}int next[s.size()];getNext(next, s);int len = s.size();//这里next[len-1] != 0也就是说该字符串存在最长相等前后缀if (next[len - 1] != 0 && len % (len - (next[len - 1] )) == 0) {return true;}return false;}
};