鱼C论坛

 找回密码
 立即注册
查看: 3271|回复: 0

[学习笔记] ★ 第三十七讲 KMP算法2 | 【接近真理前的启发】 ★

[复制链接]
发表于 2017-10-30 22:30:43 | 显示全部楼层 |阅读模式

马上注册,结交更多好友,享用更多功能^_^

您需要 登录 才可以下载或查看,没有账号?立即注册

x
本帖最后由 不二如是 于 2017-10-30 22:31 编辑


                               
登录/注册后可看大图


    


用一节课的时间,提高生活幸福感

------小甲鱼


欢乐傻笑并存

智慧邪恶同在


笔记内涵------





KMP算法之启发篇


为了照顾广大喜欢细嚼慢咽的朋友,小甲鱼再添加一讲继续深入探讨思路。

这次我们给模式匹配串添加一个k数组(也就是KMP算法中非著名的next数组)。

这是一个“智能”的数组,因为:
        他指导着模式匹配串下一步改用第几号元素去进行匹配。


Snip20171030_79.png
Snip20171030_80.png
Snip20171030_81.png
Snip20171030_82.png


KMP算法是一个非常优秀的模式匹配算法。

但是相较于其他模式匹配算法,该算法晦涩难懂

第一次接触该算法的鱼油往往会看得一头雾水,主要原因是:
        KMP算法在构造跳转表next过程中进行了多个层面的优化和抽象,使得KMP算法进行模式匹配的原理显得不那么直白。


KMP算法的核心问题:
        如何以较小的代价计算KMP算法中所用到的跳转表next


所以本次课程属于铺垫,欲知详情请看38


这位鱼油,如果喜欢本系列笔记,请订阅 专辑☞传送门)(不喜欢更要订阅

本帖被以下淘专辑推荐:

想知道小甲鱼最近在做啥?请访问 -> ilovefishc.com
回复

使用道具 举报

您需要登录后才可以回帖 登录 | 立即注册

本版积分规则

小黑屋|手机版|Archiver|鱼C工作室 ( 粤ICP备18085999号-1 | 粤公网安备 44051102000585号)

GMT+8, 2024-3-29 20:39

Powered by Discuz! X3.4

© 2001-2023 Discuz! Team.

快速回复 返回顶部 返回列表