快速上手 C++ 数据结构与算法
王健伟
《C++ 新经典》系列作者,资深 C++ 讲师
3224 人已学习
新⼈⾸单¥68
登录后,你可以任选4讲全文学习
课程目录
已完结/共 55 讲
结束语 (1讲)
快速上手 C++ 数据结构与算法
15
15
1.0x
00:00/00:00
登录|注册

43|串的KMP模式匹配算法之改进:通过优化代码解决多次重复比较问题

你好,我是王健伟。
上节课介绍的 KMP 模式匹配算法是通过 next 数组参与计算来达到加速匹配的目的。但是,在 next 数组中,因为没考虑当前字符的位置情况,只考虑了字符不匹配时单纯的指针移动问题(point1 和 point2 值的改变),这很可能导致移动后将进行比较的字符仍和上一次不匹配的字符相同导致产生多次重复的无效比较。
那这个问题要怎么解决呢?别着急,我们一步一步分析。

next 数组使用中暴露的问题

下面我会用一个相对简单点的主串和子串,通过图示说明多次重复无效比较这件事。
假设主串 S 为“aaacaaaabeg”,子串 T 为“aaaab”,可以求得子串的 next 数组为如图 1 所示:
图1 子串“aaaab”对应的next数组
主串与子串开始比较。当比较到下标为 3 的位置时,子串中的字符是 a,主串中的字符是 c,两者不同了,如图 2 所示:
图2 主串的point1指针所指向的字符c与子串point2指针所指向的字符a进行比较
依据子串的 next 数组(依据 next[3]的值),子串的 point2 指针应该恢复到子串第 3 个字符位置再用该位置的字符 a 与主串中 point1 所指向的字符 c 做比较,如图 3 所示:
图3 主串的point1指针所指向的字符c与子串point2指针所指向的字符a进行比较
图 2 中已经进行了主串中的 c 和子串中的 a 比较,而图 3 又再次进行了主串中的 c 和子串中的 a 比较,显然这第 2 次比较毫无意义。
第 2 次主串中的 c 和子串中的 a 再比较,两者还是不同,依据子串的 next 数组(依据 next[2]的值),子串的 point2 指针应该恢复到子串第 2 个字符位置再用该位置的字符 a 与主串中 point1 所指向的字符 c 作比较,如图 4 所示:
确认放弃笔记?
放弃后所记笔记将不保留。
新功能上线,你的历史笔记已初始化为私密笔记,是否一键批量公开?
批量公开的笔记不会为你同步至部落
公开
同步至部落
取消
完成
0/2000
荧光笔
直线
曲线
笔记
复制
AI
  • 深入了解
  • 翻译
    • 英语
    • 中文简体
    • 中文繁体
    • 法语
    • 德语
    • 日语
    • 韩语
    • 俄语
    • 西班牙语
    • 阿拉伯语
  • 解释
  • 总结

KMP算法改进:通过优化nextval数组,避免多余比较,提高匹配效率。文章详细说明了nextval数组取代next数组的步骤,并给出了具体例子和步骤说明。改进后的KMP算法执行效率更高,但空间复杂度未改变。 nextval数组工作原理:通过图示分析展示了主串和子串比较过程中的多余比较,指出了问题所在。改进的KMP算法使用nextval数组,通过对比next[11]和nextval[11]的值,阐述了nextval数组的优势和实际应用效果。 nextval数组求解实现代码:给出了同时求解next和nextval数组的代码实现,以及对StrKMPIndex()实现代码的升级优化。通过修改求next数组的代码,求next数组的同时也求得nextval数组也是完全可以做到的,并且可以利用nextval数组取代原来的next数组来进行子串查找。 总结:KMP算法的改进通过优化nextval数组取代next数组,避免了多余的比较,提高了匹配效率。文章详细阐述了nextval数组的工作原理和求解实现代码,为读者提供了宝贵的技术参考和实践指导。

仅可试看部分内容,如需阅读全部内容,请付费购买文章所属专栏
《快速上手 C++ 数据结构与算法》
新⼈⾸单¥68
立即购买
登录 后留言

精选留言

由作者筛选后的优质留言将会公开显示,欢迎踊跃留言。
收起评论
显示
设置
留言
收藏
沉浸
阅读
分享
手机端
快捷键
回顶部