代码随想录笔记|C++数据结构与算法学习笔记-字符串(二)|28. 实现 strStr()、459.重复的子字符串、KMP算法

卡码网.右旋字符串

卡码网题目链接
略

28. 实现 strStr()

力扣题目链接

文字链接：28. 实现 strStr()

视频链接：帮你把KMP算法学个通透！（理论篇）

KMP算法(理论)

KMP算法（Knuth-Morris-Pratt 算法）是一个著名的字符串匹配算法。

在当前对文本串和模式串检索的过程中，若出现了不匹配，如何充分利用已经匹配的部分。

然后需要搞懂以下几个概念：

前缀、后缀，最长相等前后缀、前缀表、next数组。

• 前缀：包含首字母，不包含尾字母的所有子串，都被称为前缀
• 后缀：包含尾字母，不包含首字母的所有子串，都被称为后缀
• 最长相等前后缀：是对一个字符串而言，最长的、相等的、前缀和后缀。比如说aabaa的最长相等前后缀就是2，aabaaf最长相等前后缀就是0
• 前缀表：所有前缀和整个字符串的最长相等前后缀组成的表，一般是一个序列[0, 1, 0, 1, 2, 0]
• 使用前缀表的匹配过程

设文本串txt = aabaabaaf、模式串pat = aabaaf。前缀表是[0, 1, 0, 1, 2, 0]，如果遇到不匹配，也就是说遍历到f，我们就找不包含f的前面那个子串的最长相等前后缀，是2。也就意味着，这里有一个后缀aa，前面也有一个与其相等的前缀aa。我们就找到与其相等的前缀的后面一个字符开始匹配。其实前缀的后面的那个字符的下标正好就是前缀的长度。

• next数组：其实就是存放前缀表的。

具体例子可以看上文推荐的视频。

KMP算法(代码)

构造next数组的伪代码：

void getNext(next, s)
{//初始化next数组和各个变量//j指向前缀末尾位置，同时j还指向了模式串冲突处前面子串的最长相等前后缀的长度。i指向后缀末尾位置//前缀一开始从模式串最前面的位置开始j = 0; next[0] = 0;	//next[0] = 0是因为刚开始只有一个字母a，最长相等前后缀可不就是0//以上完成了初始化，至于i的初始化是一个循环遍历的过程。for (i = 1; i < s.szie();i++){//处理前后缀不相同的情况,也就是前缀末尾和后缀末尾不匹配的时候，j应该向前会退//而且j要会退到前一位置所对应的next数组的值，也就是next[j-1]的值。//为什么要这么跳呢，就是由于之前我们将的KMP的匹配流程里就是这么跳的，所以在这里//遵循循环不变量，也这么跳s[i] != s[j];while (j > 0 && s[i] != s[j])	j = next[j-1];//这里千万不能写成if，而是while。因为我们这里是一个连续回退的过程//处理前后缀相同的情况if (s[i] == s[j]) j++;//更新next数组的值next[i] = j; }
}

C++代码

前缀表（不减一）的C++代码实现：

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()];getNext(next, needle);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++;}if (j == needle.size() ) {return (i - needle.size() + 1);}}return -1;}
};

459.重复的子字符串

力扣题目链接

文字链接：459.重复的子字符串

视频链接：字符串这么玩，可有点难度！ | LeetCode：459.重复的子字符串

暴力解法

直观的暴力解法：

枚举所有子串，然后去判断能不能构成这个字符串。

伪代码如下：

//一个for循环去获取子串的结束位置，然后继续里面的一个for循环就是拿子串去跟主串比较
for (搜索子串)for(子串去比较主串)//这里最有最有疑问的地方就是为什么一个for循环就能获取所有子串
//一般来说要两个for循环，一个用来获取子串的开始位置，另一个for循环用来获取结束位置//但其实这样是没有必要的
//我们默认这个子串是从最前面的元素开始的。所以一个for循环获取子串的终止位置就行了。 
//而且遍历的时候 都不用遍历结束，只需要遍历到中间位置，因为子串结束位置大于中间位置的话，一定不能重复组成字符串。

移动匹配

其实按照题目的说法，如果这个字符串可以由重复子串构成，那么它前半部分和后半部分肯定是想定的(不过不一定非得从中间劈开的相等)

那么如果这是个重复的字符串，那么我们从后面再重复加一遍，变成s+s，那么这个字符串中也一定是包含了一个新的s，比如s=abcabc,s+s = abc|abcabc|abc,这里就出现了一个新s。但是我们在拼接之后一定要删除首尾字母，以免搜索过程中搜到我们原来的s和后来加的s，如果这样还能找到一个s，那么说明该字符串由重复子串组成。

C++代码如下：

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;}
};

//需要注意的是，这里的t.find()其实就是用KMP算法来实现的，找某个字符串中是否包含该字符串

KMP解法

开篇一个结论：
如果字符串s = abababab

如果这个字符串是由重复子串组成的，那么它的最小重复单位，就是它的最长相等前后缀不包含的那个子串，就是它的最小重复子串。

具体讲解属实不好表达，建议直接去看视频：视频链接：字符串这么玩，可有点难度！ | LeetCode：459.重复的子字符串

等二刷的时候看能不能搞清楚算了。

C++ 代码如下：

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();if (next[len - 1] != 0 && len % (len - (next[len - 1] )) == 0) {return true;}return false;}
};