可以做头像的网站有哪些,手机上建设网站,东莞市疾控中心官网,wordpress 时间线页面文章目录 卡码网.右旋字符串28. 实现 strStr()KMP算法(理论)KMP算法(代码)C代码 459.重复的子字符串暴力解法移动匹配KMP解法 卡码网.右旋字符串
卡码网题目链接 略
28. 实现 strStr() 力扣题目链接 文字链接#xff1a;28. 实现 strStr() 视频链接#xff1a;帮你把KMP算法… 文章目录 卡码网.右旋字符串28. 实现 strStr()KMP算法(理论)KMP算法(代码)C代码 459.重复的子字符串暴力解法移动匹配KMP解法 卡码网.右旋字符串
卡码网题目链接 略
28. 实现 strStr() 力扣题目链接 文字链接28. 实现 strStr() 视频链接帮你把KMP算法学个通透理论篇 KMP算法(理论)
KMP算法Knuth-Morris-Pratt 算法是一个著名的字符串匹配算法。
在当前对文本串和模式串检索的过程中若出现了不匹配如何充分利用已经匹配的部分。
然后需要搞懂以下几个概念
前缀、后缀最长相等前后缀、前缀表、next数组。
前缀包含首字母不包含尾字母的所有子串都被称为前缀后缀包含尾字母不包含首字母的所有子串都被称为后缀最长相等前后缀是对一个字符串而言最长的、相等的、前缀和后缀。比如说aabaa的最长相等前后缀就是2aabaaf最长相等前后缀就是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.重复的子字符串 视频链接字符串这么玩可有点难度 | LeetCode459.重复的子字符串 暴力解法
直观的暴力解法
枚举所有子串然后去判断能不能构成这个字符串。
伪代码如下
//一个for循环去获取子串的结束位置然后继续里面的一个for循环就是拿子串去跟主串比较
for (搜索子串)for(子串去比较主串)//这里最有最有疑问的地方就是为什么一个for循环就能获取所有子串
//一般来说要两个for循环一个用来获取子串的开始位置另一个for循环用来获取结束位置//但其实这样是没有必要的
//我们默认这个子串是从最前面的元素开始的。所以一个for循环获取子串的终止位置就行了。
//而且遍历的时候 都不用遍历结束只需要遍历到中间位置因为子串结束位置大于中间位置的话一定不能重复组成字符串。移动匹配
其实按照题目的说法如果这个字符串可以由重复子串构成那么它前半部分和后半部分肯定是想定的(不过不一定非得从中间劈开的相等)
那么如果这是个重复的字符串那么我们从后面再重复加一遍变成ss那么这个字符串中也一定是包含了一个新的s比如sabcabc,ss 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
如果这个字符串是由重复子串组成的那么它的最小重复单位就是它的最长相等前后缀不包含的那个子串就是它的最小重复子串。
具体讲解属实不好表达建议直接去看视频视频链接字符串这么玩可有点难度 | LeetCode459.重复的子字符串
等二刷的时候看能不能搞清楚算了。
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;}
};
