KMP简介以及反证法证明在KMP算法中,模式串的快速移动一定不会错过正确匹配位置

算法中,模式串的快速移动一定不会错过正确匹配位置"/>

KMP简介以及反证法证明在KMP算法中,模式串的快速移动一定不会错过正确匹配位置

KMP算法

预备知识:

前缀表(next数组) 建议先了解前缀表概念了解后再阅读本文

文本串(被匹配的长串)

模式串(子串)

失配(在文本串与模式串匹配的过程中,不匹配的那个字符位置)

1.什么是KMP算法:

     通过前缀表的预处理,加速模式串移动的速度,达到时间复杂度的缩减.

2.KMP算法的由来:

     关于字符串匹配这一方面,首先我们能想到的方法也就是最简单的方法就是暴力匹配,但是暴力匹配这一算法的时间复杂度非常高,达到了N的平方阶,那我们很容易想到怎么使模式串的移动加速呢?第一个想法是我们将模式串直接移动到失配位置,这样我们能大幅度的增速,但是很可惜,这个方法是错误的. 下面举例说明:

如图,我们有一个文本串需要匹配一个模式串:

显然如果我们使用暴力匹配,肯定时间复杂度是不过关的.

如果我们在每次失配的位置,直接将字符串进行整体移动,则会出现以下情况:

没错,我们错过了一次正确的匹配,所以这种方法显然是行不通的.

因此,我们知道了缩短时间复杂度的最大问题,什么问题?

如何在不错过正确匹配的前提条件下加速模式串的移动!

3.KMP算法为什么能加速:

我们知道KMP算法最重要的部分就是前缀表的计算:

也就是计算模式串的每个子串的最长公共前后缀长度

为什么要计算子串的公共前后缀长度呢?

我们看下图:

我们在暴力匹配的算法中每次移动模式串只能移动一次,因为我们害怕错过正确匹配的位置.

但是在KMP算法中,我们已经计算出了前缀表,我们移动的距离就改成了前缀表的数值:

我们可以直接将公共前缀部分移动到公共后缀部分:

这样我们就可以大大加速模式串的移动速度,指针也不需要在文本串中回溯,从而使时间复杂度达到O(m+n)

那我们心里又多出了一个疑问:为什么我们不能直接移动到失配位置呢,这种移动和直接移动到失配位置有什么区别呢?

为什么这种移动能保证中间不错误正确匹配呢? 没错,这就是我们今天要讲的重点!

4.利用反证法论证在KMP算法中,模式串的快速移动不会错过正确匹配位置

        假设我们在一次移动过程中移动了N个字符长度.即将最长公共前缀移动到最长公共后缀的歩长为N.最大公共前后缀的长度为Z.

        假设在在N-X步长时,我们错过了 一次正确匹配.会出现下图情况,最大公共前后缀长度变成了Z+X.

为什么?

假设匹配成功,上层文本串存在被匹配的部分,既然以及匹配成功,那么Z+X部分上下一定相同,所以Z+X现在成为了最大公共前后缀.

而Z是我们通过前缀表得到的,如果存在上述假设情况,则实际公共前后缀长度与前缀表不符,与事实出现矛盾.所以假设不成立.

由此论证出KMP算法能在快速移动模式串的同时保证不错过正确匹配位置,从而达到将时间复杂度又O(n2) -> O(m+n)的效果.