今日任务
- 实现 strStr()
- 重复的子字符串
- 字符串总结
- 双指针回顾
详细布置
28. 实现 strStr() (本题可以跳过)
因为KMP算法很难,大家别奢求 一次就把kmp全理解了,大家刚学KMP一定会有各种各样的疑问,先留着,别期望立刻啃明白,第一遍了解大概思路,二刷的时候,再看KMP会 好懂很多。
或者说大家可以放弃一刷可以不看KMP,今天来回顾一下之前的算法题目就可以。
因为大家 算法能力还没到,细扣 很难的算法,会把自己绕进去,就算别人给解释,只会激发出更多的问题和疑惑。所以大家先了解大体过程,知道这么回事, 等自己有 算法基础和思维了,在看多看几遍视频,慢慢就理解了。
题目链接/文章讲解/视频讲解:https://programmercarl.com/0028.%E5%AE%9E%E7%8E%B0strStr.html
Tips:照着KMP的代码敲了一遍,感觉还是有点一知半解,个人感觉前缀表不减一的版本更好理解一些,之后可以多看几遍。
总体来说就是两个过程:
1. 建立前缀表
2. 根据前缀表进行比对
我的题解:
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[j] == s[i]){
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++; // i++在for循环里
}
if(j == needle.size()){
return i - needle.size() + 1;
}
}
return -1;
}
};
459.重复的子字符串 (本题可以跳过)
本题算是KMP算法的一个应用,不过 对KMP了解不够熟练的话,理解本题就难很多。
我的建议是 KMP和本题,一刷的时候 ,可以适当放过,了解怎么回事就行,二刷的时候再来硬啃
题目链接/文章讲解/视频讲解:https://programmercarl.com/0459.%E9%87%8D%E5%A4%8D%E7%9A%84%E5%AD%90%E5%AD%97%E7%AC%A6%E4%B8%B2.html
Tips:
我的题解:
字符串总结
比较简单,大家读一遍就行
题目链接/文章讲解:https://programmercarl.com/%E5%AD%97%E7%AC%A6%E4%B8%B2%E6%80%BB%E7%BB%93.html
双指针回顾
此时我们已经做过10到双指针的题目了,来一起回顾一下,大家自己也总结一下双指针的心得
文章讲解:https://programmercarl.com/%E5%8F%8C%E6%8C%87%E9%92%88%E6%80%BB%E7%BB%93.html
标签:459,strStr,int,needle,28,E7%,next,E5%,KMP From: https://www.cnblogs.com/GavinGYM/p/17029193.html