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

Question

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

Answer 1

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

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

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

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

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

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

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

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

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

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