KMP算法
28. 实现 strStr()【简单，KMP】
思路一：BF法，即朴素匹配，暴力破解
时间复杂度：O(nm)
空间复杂度：O(1)
class Solution {
public:
int strStr(string haystack, string needle) {
if (needle.size() > haystack.size()) return -1; //排除子串比主串长的情况
if (needle.size() == 0) return 0; //排除子串为空串的情况
int i = 0, j = 0;
while (i < haystack.size() && j < needle.size()) {
if (haystack[i] == needle[j]) { //1.两字符相等则继续匹配
i++;
j++;
}
else { //主串起始位置右移，子串置位
i = i - j + 1; //移动一位再匹配
j = 0; //退回子串首位
}
}
if (j == needle.size()) return i - j; //2.子串中所有字符都匹配到了，就返回咯
return -1; //未匹配到
}
};
优化
//for循环比while循环性能好，主要体现在n-m上
class Solution {
public:
int strStr(string haystack, string needle) {
if (needle.size() == 0) return 0;
int n = haystack.size(), m = needle.size();
for (int i = 0; i <= n - m; i++) { //注意这里的n-m 后面有子串比主串上的情况就不需要匹配了
for (int j = 0; j < m; j++) { //遍历子串
if (haystack[i + j] != needle[j]) break;
if (j == m - 1) return i; //子串全部匹配到
}
}
return -1;
}
};
思路二：KMP算法
字符串唯一一个难的算法，重点！！！
KMP算法视频讲解：https://www.bilibili.com/video/BV1PD4y1o7nd?spm_id_from=333.999.0.0
KMP算法文档讲解：参考代码随想录
前缀表：用来回退的，它记录了子串与主串不匹配的时候，子串应该从哪里开始重新匹配
怎么制作前缀表：最长相等前后缀
[外链图片转存失败,源站可能有防盗链机制,建议将图片保存下来直接上传(img-a78bFmWK-1640348559509)(https://gitee.com/zdbya/picgo_image/raw/master/SSL_img/202112241725788.gif)]
前缀表记录的是不匹配时需要回退到哪里重新开始匹配
什么是next数组：next数组就是前缀表，但是很多实现都是把前缀表统一减1作为next数组；或者前缀表整体右移
[外链图片转存失败,源站可能有防盗链机制,建议将图片保存下来直接上传(img-vldCy8xZ-1640348559509)(https://gitee.com/zdbya/picgo_image/raw/master/SSL_img/202112241730223.gif)]
时间复杂度：O(n+m)
空间复杂度：O(m)，子串的长度，制作next数组
制作next数组
定义两个指针i和j，j指向前缀起始位置，i指向后缀起始位置。
统一减一版本
void getNext(int* next, const string& s){
int j = -1;
next[0] = j;
for(int i = 1; i < s.size(); i++) { // 注意i从1开始
while (j >= 0 && s[i] != s[j + 1]) { // 前后缀不相同了
j = next[j]; // 向前回退
}
if (s[i] == s[j + 1]) { // 找到相同的前后缀
j++;
}
next[i] = j; // 将j（前缀的长度）赋给next[i]
}
}
[外链图片转存失败,源站可能有防盗链机制,建议将图片保存下来直接上传(img-RQA2sAVX-1640348559510)(https://gitee.com/zdbya/picgo_image/raw/master/SSL_img/202112241751184.gif)]
不减一版本
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;
}
}
前缀表统一减一 版本
class Solution {
public:
//获取next数组的函数 统一-1版本
void getNext(int* next, const string& s) {
int j = -1;
next[0] = j;
for(int i = 1; i < s.size(); i++) { // 注意i从1开始
while (j >= 0 && s[i] != s[j + 1]) { // 前后缀不相同了
j = next[j]; // 向前回退
}
if (s[i] == s[j + 1]) { // 找到相同的前后缀
j++;
}
next[i] = j; // 将j（前缀的长度）赋给next[i]
}
}
int strStr(string haystack, string needle) {
if (needle.size() == 0) return 0; //排除特殊情况
int next[needle.size()];
getNext(next, needle); //1.获取next数组
int j = -1; // 因为next数组里记录的起始位置为-1
for (int i = 0; i < haystack.size(); i++) { // 注意i就从0开始
while(j >= 0 && haystack[i] != needle[j + 1]) { // 不匹配
j = next[j]; // j寻找之前匹配的位置
}
if (haystack[i] == needle[j + 1]) { // 匹配，j和i同时向后移动
j++; // i的增加在for循环里
}
if (j == (needle.size() - 1) ) { // 文本串s里出现了模式串t
return (i - needle.size() + 1);
}
}
return -1;
}
};
前缀表不减一版本
背下来这个版本代码
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); //1.获取next数组
int j = 0;
for (int i = 0; i < haystack.size(); i++) {
while(j > 0 && haystack[i] != needle[j]) { // 不匹配
j = next[j - 1]; // j寻找之前匹配的位置
}
if (haystack[i] == needle[j]) { // 匹配，j和i同时向后移动
j++;
}
if (j == needle.size() ) { //子串匹配完成
return (i - needle.size() + 1);
}
}
return -1;
}
};
459. 重复的子字符串【简单】
方法一：暴力枚举
//时间复杂度：O(n^2)
//空间复杂度：O(1)
class Solution {
public:
bool repeatedSubstringPattern(string s) {
int n = s.size();
for (int i = 1; i <= n/2; ++i) { //枚举子串的长度
if (n % i != 0) continue; //主串的长度必须是子串长度的倍数
for (int j = i; j < n; ++j) { //遍历主串
if (s[j] != s[j % i]) { //串以i为一个周期
break;
}
if (j == n - 1) return true;
}
}
return false;
}
};
方法二：字符串查找
/*
* 双倍字符串解决；
* 从索引1开始查找
* 查找单倍字符串的位置 是否在 第二个字符串开始的位置
* 是，则 false
* 否，则 true
*/
class Solution {
public:
bool repeatedSubstringPattern(string s) {
return (s + s).find(s, 1) != s.size();
}
};
方法三：kmp实现方法二的find函数
需要掌握方法二的思路，然后用kmp做；在kmp基础上修改成这题能用的
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;
}
}
bool kmp(string haystack, string needle) {
if (needle.size() == 0) return 0; //排除特殊情况
int next[needle.size()];
getNext(next, needle); //1.获取next数组
int j = 0;
for (int i = 1; i < haystack.size(); i++) {
while (j > 0 && haystack[i] != needle[j]) { // 不匹配
j = next[j - 1]; // j寻找之前匹配的位置
}
if (haystack[i] == needle[j]) { // 匹配，j和i同时向后移动
j++;
}
if (j == needle.size()) { //子串匹配完成
if (i == haystack.size() - 1) { //但是遍历完了主串
return false;
}
return true;
}
}
return false;
}
bool repeatedSubstringPattern(string s) {
return kmp(s + s, s);
}
};
但是这题的next数组会有一个规律
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;
}
}
bool repeatedSubstringPattern(string s) {
if (s.size() == 0) return 0; //排除特殊情况
int next[s.size()];
getNext(next, s); //1.获取next数组
int len = s.size();
if(next[len-1] != 0 && len % (len - next[len-1]) == 0){
return true;
}
return false;
}
};
这便是最简洁的方法