当前位置:鱼C工作室 >数据结构和算法 > 查看文章

KMP算法(养成篇) – 数据结构和算法36

KMP算法(养成篇)

 

让编程改变世界

Change the world by program


 

KMP算法

 

相信很多鱼油(包括小甲鱼自己)在刚开始接触KMP算法的时候始终是丈二和尚摸不着头脑,要么完全不知所云,要么看不懂书上的解释,要么自己觉得好像心里了解KMP算法的意思,却说不出个究竟,所谓知其然不知其所以然是也。

 

KMP算法对大多数初学者来言是一项比较巨大的考验,特别是自学算法的朋友,很多资料对数学功底不牢固的学者来说看起来比较模糊。

所以,小甲鱼在讲解这一算法的实现前,特地添加了这一篇章:最高作战方针之算法思路养成篇!

 

KMP算法是三位老前辈(D.E.Knuth、J.H.Morris 和 V.R.Pratt)的研究结果,大大的避免重复遍历的情况,全称叫做克努特-莫里斯-普拉特算法,简称KMP算法或看毛片算法。

 

上节课我们谈了BF算法,也说了BF算法虽然很黄很暴力,但是效率却不搞。

我们也给了一个例子。但似乎那个例子不足以反映出导致这种算法效率低下的致命缺陷。

 

因此,我们用下边一个例子来继续探讨:

 

 

回溯就是坚持条条大路通罗马的决心,然后遇到挫折就回到跌倒的地方重新爬起来,继续往前,这种思想是好的,但效率是低的。

因为牛在耕田的时候也是这么想的,但人家袁隆平懂得找捷径,才有了超级杂交水稻,这也告诉我们鱼油,学习除了勤奋,除了必要坚持,还更需要思考!

 

KMP算法的核心就是避免不必要的回溯,那么什么是不必要的呢?问题由模式串决定,不是由目标决定!

 

思路启发一

 

 

思路启发二

 

 

分页阅读: 1 2 下一页
为您推荐

报歉!评论已关闭.