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算法文档讲解：参考代码随想录
前缀表：用来回退的，它记录了子串与主串不匹配的时候，子串应该从哪里开始重新匹配
怎么制作前缀表：最长相等前后缀
前缀表记录的是不匹配时需要回退到哪里重新开始匹配
什么是next数组：next数组就是前缀表，但是很多实现都是把前缀表统一减1作为next数组；或者前缀表整体右移
时间复杂度：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] } }
不减一版本
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; } };
这便是最简洁的方法
