阅读 16

KMP算法证明

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

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算法是直接从ba1的比较开始,而需要比较yx了。这些文章的证明点就是xy是相等的,因为失败点是b-c,这时就说明了xy是相等的了,这一点很容易看出来。

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

示例说明:

源字符串source,简称S,是被匹配的字符串,模式串pattern,简称p,是较小的那个字符串。 对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;

next[i]值就是存在一个值k,使得(0, k-1)这一段跟(i-k+1,i)这一段是一模一样的。

再往后移一位:

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值是满足条件里最大的那个,所以更小值它是可能满足条件的。但那就是下一次匹配之后的问题了,现在只是剔除掉一些绝对不可能的情况。

关注下面的标签,发现更多相似文章
评论