KMP算法难度较大,在理解时会有很大的难度,在这里建议大家参考LeetCode28. 实现 strStr()、LeetCode459.重复的子字符串两个题目,并参照代码随想录进一步理解
网址如下:
LeetCode28文章讲解
https://programmercarl.com/0028.%E5%AE%9E%E7%8E%B0strStr.html
LeetCode459文章讲解
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
本文中预先附上KMP算法的相关代码,供大家学习参考
(二刷再战)
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]
}
}
总结篇
字符串的内容相对来说比较简单,总的来看考察题型分为这几种:
字符串的基本操作
库函数的相关使用
双指针法
反转系列
KMP算法的相关应用(重点)
字符串类类型的题目,往往想法比较简单,但是实现起来并不容易,复杂的字符串题目非常考验对代码的掌控能力。
特别注意双指针法是字符串处理的常客。
加油💪!
你是否还在寻找稳定的海外服务器提供商?创新互联www.cdcxhl.cn海外机房具备T级流量清洗系统配攻击溯源,准确流量调度确保服务器高可用性,企业级服务器适合批量采购,新人活动首月15元起,快前往官网查看详情吧
当前文章:代码随想录算法训练营第九天|KMP算法略讲与字符串总结-创新互联
分享链接:https://www.cdcxhl.com/article14/djdoge.html
成都网站建设公司_创新互联,为您提供搜索引擎优化、品牌网站制作、网站营销、微信公众号、网站策划、自适应网站
声明:本网站发布的内容(图片、视频和文字)以用户投稿、用户转载内容为主,如果涉及侵权请尽快告知,我们将会在第一时间删除。文章观点不代表本网站立场,如需处理请联系客服。电话:028-86922220;邮箱:631063699@qq.com。内容未经允许不得转载,或转载时需注明来源: 创新互联