KMP算法证明

背景

了解KMP算法的直接看证明。

字符串s,模式字符串p,想要在s中找到第一个子串等于p

穷举解法：

p的开头跟s的开头比较，相等就一个个往下对比，遇到出错的就p往后移动一位，即p的开头和s的第二个字符开始比。一次类推直到找到。

KMP:

假设某次匹配中失败的位置在p中是j,用S(i,j)表示S从i到j的子串，则对p有这样的性质：p(0,k-1) = p(j-k,j-1), 0 <= k < j。语言描述为：在j的前面紧贴着一段k长度的子串，跟p开头的长度为k子串是一样的。

比如 abcabd, j为5时，即d的位置，它前面的ab和开头的ab相等，所以j为2。如果存在多种这样的情况，k取最大的，比如aaacaaab,对最后的b而言，1、2、3都是成立的，取3。如果不存在这样的，则k=0。而k==j的时候，等式两边是同一个子串，没有比较的意义了。

对模式串里每一个j都有这样的k，使用next[j]来表示。

假设失败位置在s中是i,在p中是j,KMP算法的优化就在于，失败了之后，下一次的比较，s从i开始，p从next[j]开始。

举例：

frabcabxabcabd              字符串s
  abcabd                    模式串p

在x-d位置失败了，如果是穷举法，下一步是：

frabcabxabcabd              字符串s
   abcabd                   模式串p 

p后移了一位，然后从头开始比。而KMP算法是：

frabcabxabcabd              字符串s
     abcabd                 模式串p 

失败位置在s中是x，在p中是d,索引为5，上面分析过了d的next[5]=2。所以p从p[2]即c的位置开始比，s保留上次失败的位置，也就是x,所以就成了现在的样子。

这样一下子就跳过很多位，优化点就在这里。

证明

看了很多网上的证明，它们的关注点都错了，它们证明的是什么呢？

x a1 a2 y b
x a1 a2 x c

失败点是最后的b-c,然后c前面的x和开头的x是相同的，这个x就是next[j]的那一段，KMP下次比较调整后为：

x a1 a2 y b
        x a1 a2 x c

KMP算法是直接从b和a1的比较开始，而需要比较y和x了。这些文章的证明点就是x和y是相等的，因为失败点是b-c,这时就说明了x和y是相等的了，这一点很容易看出来。

但问题是为什么可以直接跳过这么多位置呢？为什么移动一个位置来比较就一定会失败呢？这个才是这个算法最需要证明的地方吧。就这个例子里，为什么x不用和a1比？为什么不用和a2比呢？

示例说明：

对p有p1 p2 p3 p4 px py...,然后在px失败了，这就意味着它之前p1-p4都是匹配到的,那假设S中对应的字符为:p1 p2 p3 p4 s1 s2...,移动一位后：

p1 p2 p3 p4 s1 s2...
   p1 p2 p3 p4 px py...

假如这个时候匹配成功，那么就有p2 p3 p4 = p1 p2 p3,根据前面对next值的定义，这时对px它的next值就是3；

再往后移一位：

p1 p2 p3 p4 s1 s2...
       p1 p2 p3 p4 px py...

如果这时匹配成功，那么p3 p4=p1 p2,那px的next值就是2。而如果我们已经知道了px的next值为1，就可以判断出这两种情况是不可能匹配成功的。

即匹配失败后，每往后移动一步如果成功，都有一个对应的next值，而且这个next值是严格递减的，所以知道实际的next值之后，更大的next就必定是不可能的，那么之前的移动也就是不可能匹配成功的。

更小的有没有可能？ 有，因为next值是满足条件里最大的那个，所以更小值它是可能满足条件的。但那就是下一次匹配之后的问题了，现在只是剔除掉一些绝对不可能的情况。