最近在学kmp算法,但是好难理解

最近在学kmp算法,但是看了网上好多的讲解,都觉得好乱,有谁能给一个比较容易理解的版本么? 谢谢啦!

kmp

4个回答

我理解中的kmp算法是这样的。kmp算法的核心是部分匹配表。那什么是部分匹配表呢? 看下去 。。

比如字符串“ababaab” ,它的部分匹配表为0012312,每个数对应一个字符。

如果不理解这个,先不要紧,看下去,先明白怎么求部分匹配表

我来定义一个最优前缀和最优后缀,对于字符串,如果它的前缀等于后缀,并且是长度最长的,那么称为最优前缀,最优后缀。。举个例子,比如字符串"ababa", 它的前缀有a,ab,aba,abab,后缀有a,ba,aba,baba,可以知道最优前缀为aba,因为它在后缀出现,且长度最大。

现在明白怎么求部分匹配表了吧 。。

接下来讲部分匹配表可以干嘛。。。

首先对比于朴素匹配算法,如果匹配失败了,就只是右移一位,然后继续比较,这样的时间复杂度是n^2的,而且做了好多无意义的比较。

有了部分匹配表,因为知道最优前缀和最优后缀,那么其实如果匹配失败的化,前面一段区间的字符串我们已经知道有几个已经匹配了。

比如字符串"ababaab"来匹配"ababaacababaab",可以看到在第7个字符匹配失败。那么下一次匹配的点在哪了?朴素匹配算法是重新开始,这很傻。。。

我们知道前5个字符ababa,它有最优前缀aba,我们可以知道他会匹配到后缀aba,那么就可以直接跳到那个位置了。。。
说到这里了,你可以在纸上画画图,看一看。希望可以帮到你。

Wintermelob
Wintermelob 不过还是有点晕 我消化消化吧 嘻嘻
4 年多之前 回复
Wintermelob
Wintermelob 谢谢大神 你的理解我还是第一次看到
4 年多之前 回复

如果你只是考虑工作,那么到时候用kmp的时候一般就是网上找代码,不会要你自己写, 如果你想学kmp的算法思路, 那么你最好先理解kmp的思想,不要先看代码, 然后自己写代码,也不用卡在这里, 等你学了以后的东西在回头看就会觉得简单了, 当然,kmp算法其实也已经被优化好多次了。 一个曾经也被kmp弄得头晕的解答~

kmp算法用来匹配字符串,它的核心思想就是在匹配不成功的时候,以尽可能少的回溯的代码继续匹配。

参考:http://blog.csdn.net/tukangzheng/article/details/38438481/ 这文章的图可以帮助你理解。

有时候需要靠耐心,自己动手拿笔在纸上多画画图,举几个例子跟着教材练习,自然就懂了。
多动手,多思考,不能光看不练。最好能自己编码实现算法,然后做测试,测试不通过时,审查问题,修正。。。反复实践。。。。

http://blog.csdn.net/power721/article/details/6132380

http://blog.csdn.net/joylnwang/article/details/6778316/

Csdn user default icon
上传中...
上传图片
插入图片
抄袭、复制答案,以达到刷声望分或其他目的的行为,在CSDN问答是严格禁止的,一经发现立刻封号。是时候展现真正的技术了!
立即提问
相关内容推荐