如何理解KMP算法

感觉一点都不难/摊手

KMP算法的核心是next数组.理解了这个,就很容易理解KMP的原理.

在说next数组之前,先要理解一个字符串的前缀和后缀.

例如对于字符串”asdfgh”,它的前缀就是

{asdfg,asdf,asd,as,a}

后缀则是

{s,sd,sdf,sdfg,sdfgh}

那么next数组怎么求呢,首先是通过求一个部分匹配表PMT(Partial Match Table).

例如字符串”aabbaabb”的匹配表

|char |a |a |b |b |a |a |b |b |
|index |0 |1 |2 |3 |4 |5 |6 |7 |
|PMT |0 |0 |0 |3 |3 |0 |0 |0 |

很显然,可以看出PMT[i]的值就是char[i]的前缀和后缀最长的公共字串的长度

然后再来说一下根据部分匹配表加速匹配的原理.举个例子在s1”ababababac”中匹配s2”abababac”(如图),当在i出匹配发生错误的时候,s1[i]之前的next[j - 1]个字符与s2[0]——s2[next[j - 1]]是相同的,也就是i - j 到 i 这一段是相同的,根据PMT数组的定义,这个长度就是前缀后缀交集的最长子串,因此下一次比较的时候,就不需要来比较这一部分.

当然为了编程的方便,我们并不是直接使用PMT数组,而是将其中每一个位都后移,将第0位补充为0.

如下表:

|char |a |a |b |b |a |a |b |b |
|index |0 |1 |2 |3 |4 |5 |6 |7 |
|PMT |0 |0 |0 |3 |3 |0 |0 |0 |
|next |-1|0|0|0 |3 |3 |0 |0|

相关代码见GitHub

script>