111qqz的小窝

老年咸鱼冲锋!

KMP算法学习

20170801update:当时竟然没有强调next函数的含义?

next[i]的含义是,i之前的整个前缀中,最长的该前缀的前缀和后缀相同的长度。

看图:

 

KMP感觉是我学到现在最难懂的一个算法了QAQ
为什么你们都那么强啊,看几个小时就看懂了…

 

先放一波我觉得值得看的资料:
kmp算法讲解(配图比较全….)
kmp学习资料2

 

说下我对kmp算法的理解:

理解kmp算法大概分成两个部分。

一部分是理解一个naive的kmp算法,可以叫”fast slide” algorithm

思想大概就是,当mismatch发生时,我们并不是一无所有,而是知道在mismatch发生前所匹配的字符的信息的。

然后知道这些信息我们可以做什么呢?

先观察一下最最暴力的求解字符串匹配的算法:

这个算法低效在,当mismatch发生时,我只是往前移动了一个字符。

Screenshot from 2016-08-08 21-03-22

因此我们定义了 maxoverlap函数。。

Screenshot from 2016-08-08 21-05-51

需要特别强调的是:

Screenshot from 2016-08-08 21-08-22

 

 

这样我们就可以利用maxoverlap函数来优化当mismatch发生的时候,移动的过程。

这样我们就得到了“fast slide” algorithm算法

 

但是。。。能不能再给力一点呢

再给力一点

我们发现,上述代码中,我们每次都要计算一次maxoverlap函数…

但是。 。一个字符串。。。它的子串个数是有限的。。。

我们能不能加速这个过程呢。。。

很容易想到预处理一波。。。

也就是求所谓的failure function ,中文应该叫失配函数…

 

Screenshot from 2016-08-08 21-19-04

 

所以第二部分就是如何快速求出失配函数

这也是我认为的kmp算法最精(nan)髓(dong)的地方。

说点什么

您将是第一位评论人!

提醒
wpDiscuz