Skip to content

KMP算法学习初步

kmp

最近花了些时间学习kmp算法(看毛片算法),对于没有基础的人来说,开始学一个东西都会非常痛苦,我也是这样。反反复复读了好久相关的文章,终于有些明白是怎么回事了,这里给大家推荐下我的学习路径。

首先,我推荐大家看阮一峰的博客文章——字符串匹配的kmp算法

这篇文章篇幅不长,但写得非常清楚明白,文章中用例子给出了kmp到底是怎么操作的一个过程,不过并没有给出代码。我自己看懂了以后,就直接写了一个kmp,当然这是初级版的kmp,写得比较啰嗦,而且优化的不是很好,不过毕竟能写了呀。

其次,我再推荐大家看matrix67的文章——kmp算法详解

阮一峰的博客主要讲具体实现过程,而matrix67则简单介绍了kmp的原理是怎么回事,而且其中还给出了伪代码,也就是优化以后的kmp写法。我自己在看的时候,其实对匹配数组用前面推出后面的内容理解得不是很明白,所以我又从另外一篇   从头到尾彻底理解kmp   对照着看,这篇文章讲了实现,也讲了原理,后面还有实际代码给出,只不过篇幅比较长,容易看着看着就没耐心。

这三篇文章,他们对于匹配数组(next数组)具体的定义并不全然相同,但本质是一回事。

阮一峰定义匹配数组是前后缀最大公共子列,然后移动位数用已匹配的字符数-匹配数组的值。而matrix67则是如果后一位不匹配,就移动到哪一位,后两篇博客的next数组其实就是前后移了一位,本质相同,阮一峰的匹配就是把他们移位的情况在具体分解出来,怎么移位的告诉大家,所以本质上,他们都相同。

看完这些以后,我自己对kmp就有初步的理解,自己也能裸敲出matrix67的那套代码,接下来就是敲敲题来巩固了。

下面是我的代码:

看完阮一峰博客后写得:kmp第一次

后来写得:kmp最终版

Post a Comment

Your email is never published nor shared. Required fields are marked *
*
*