湖北网站建设,企业网站建设的目的,网页qq怎么登录界面,绵阳市住房和城乡建设局网站代码随想录二刷Day9
今日任务
28.找出字符串中第一个匹配项的下标 459.重复的子字符串 字符串总结 双指针总结 语言#xff1a;C
KMP
链接#xff1a;https://programmercarl.com/0459.重复的子字符串.html#kmp
用处#xff1a;当出现字符串不匹配时#xff0c;可以利…代码随想录二刷Day9
今日任务
28.找出字符串中第一个匹配项的下标 459.重复的子字符串 字符串总结 双指针总结 语言C
KMP
链接https://programmercarl.com/0459.重复的子字符串.html#kmp
用处当出现字符串不匹配时可以利用一部分之前已经匹配的内容节省匹配时间避免从头匹配前缀表用来回退的即记录当模式串与主串不匹配时模式串应该从哪个位置开始重新匹配记录下标i之前包括i的字符串中有多大长度的相同前缀后缀最长相等前后缀前缀指不包含最后一个字符的所有以第一个字符开头的连续子串后缀指不包含第一个字符的所有以最后一个字符结尾的连续子串前缀表要求的是相同前后缀的长度前缀表为什么可以确定匹配失败后跳到哪里重新匹配 前缀表利用的是相同前后缀所以如果在某个位置匹配失败后可以根据前缀表找到失败位置后缀对应的前缀位置直接跳到前缀相应位置重新匹配即可前缀表和next数组之间的关系 next数组可以是前缀表也可以是前缀表统一减1的结果和KMP原理无关主要是根据实现方便程度修改的时间复杂度O(mn)模式串长度为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(vectorint 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;vectorint 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(vectorint 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) {vectorint next(s.length());getNext(next, s);if(next[next.size() - 1] 0) return false; //abacint len s.length() - next[next.size() - 1];if(len ! 0 s.length() % len 0) return true;return false;}
};
