【代码随想录二刷】Day9-字符串-C++
代码随想录二刷Day9
今日任务
28.找出字符串中第一个匹配项的下标
459.重复的子字符串
字符串总结
双指针总结
语言：C++
KMP
链接：https://programmercarl.com/0459.重复的子字符串.html#kmp
- 用处：当出现字符串不匹配时，可以利用一部分之前已经匹配的内容，节省匹配时间，避免从头匹配
- 前缀表：用来回退的，即记录当模式串与主串不匹配时，模式串应该从哪个位置开始重新匹配；记录下标i之前（包括i）的字符串中，有多大长度的相同前缀后缀
- 最长相等前后缀：前缀指不包含最后一个字符的所有以第一个字符开头的连续子串；后缀指不包含第一个字符的所有以最后一个字符结尾的连续子串；前缀表要求的是相同前后缀的长度
- 前缀表为什么可以确定匹配失败后跳到哪里重新匹配？
前缀表利用的是相同前后缀，所以如果在某个位置匹配失败后，可以根据前缀表找到失败位置后缀对应的前缀位置，直接跳到前缀相应位置重新匹配即可 - 前缀表和next数组之间的关系？
next数组可以是前缀表，也可以是前缀表统一减1的结果，和KMP原理无关，主要是根据实现方便程度修改的 - 时间复杂度：O(m+n)，模式串长度为m，文本串长度为n，建立模式串的时间复杂度为O(m)，文本串匹配的时间复杂度为O(n)
- next数组构造过程：初始化，处理前后缀不同的情况，处理前后缀相同的情况，更新next数组
void getNext(int* next, string& s){int i = 0; //i表示最大前缀长度，初始化为0next[0] = i;for(int j = 1; j < s.length(); j++){ //j表示最大后缀长度，从1开始//处理前后缀不同的情况while(i > 0 && s[i] != s[j]){i = next[i - 1];}if(s[i] == s[j]){i++;}next[j] = i;}
}
}
28. 找出字符串中第一个匹配项的下标
链接：https://leetcode.cn/problems/find-the-index-of-the-first-occurrence-in-a-string/
class Solution {
public:void getNext(vector<int>& next, string& s){int i = 0;next[0] = i;for(int j = 1; j < s.length(); j++){while(i > 0 && s[i] != s[j]){i = next[i - 1];}if(s[i] == s[j]){i++;}next[j] = i;}}int strStr(string haystack, string needle) {int res = -1;vector<int> next(needle.length());getNext(next, needle);int j = 0; //needlefor(int i = 0; i < haystack.length(); i++){ //haystackwhile(j < next.size() && haystack[i] == needle[j]){i++;j++;}if(j > 0 && j < next.size() && haystack[i] != needle[j]){j = next[j - 1];i--; //这里要减1，否则会错位，比较推荐下面的写法}else if(j == next.size()){res = i - needle.length();break;}}//另一种写法/*for(int i = 0; i < haystack.length(); i++){ //haystackwhile(j > 0 && j < next.size() && haystack[i] != needle[j]){j = next[j - 1];}if(j < next.size() && haystack[i] == needle[j]){j++;}if(j == next.size()){res = i - needle.length() + 1;break;}}*/return res;}
};
459. 重复的子字符串
链接：https://leetcode.cn/problems/repeated-substring-pattern/
若一个字符串由重复子串构成，则最长相等前后缀不包含的子串就是最小重复子串，接下来可以根据长度关系简单判断字符串是否由重复子串构成
class Solution {
public:void getNext(vector<int>& next, string& s){int i = 0;next[0] = i;for(int j = 1; j < s.length(); j++){while(i > 0 && s[i] != s[j]){i = next[i - 1];}if(s[i] == s[j]){i++;}next[j] = i;}}bool repeatedSubstringPattern(string s) {vector<int> next(s.length());getNext(next, s);if(next[next.size() - 1] == 0) return false; //"abac"int len = s.length() - next[next.size() - 1];if(len != 0 && s.length() % len == 0) return true;return false;}
};