KMP算法的next/nextval值的个人理解

2020年4月1日11:51:50 发表评论 185 views

学习KMP算法的时候对于next/nextval值的计算总是处在似懂非懂的状态,后面结合了老师的方法和网上的资料自己总结了一下,下面是我自己的一些个人经验,比较浅显易懂,希望能帮到一部分人。

KMP算法的运行模式

KMP算法与BF算法的最大区别就是,BF算法每次匹配时模式串都是往下一位移动,又重新从模式串的第一位开始比对;而KMP算法的思想是,如果已有一部分字段匹配成功,在这一部分字段中寻找相同的两部分小字段,即概念中的子串,以减少比较次数,提升算法效率。

但是,

这两部分相同的子串,是有约束条件的。

计算next与nextval值

我们以串测试中的第7题为例,以下方法计算得的next与nextval值均遵循考试规则,可能不同教材有所不同。

注意:务必看完整个过程,切勿心急

在我们计算之前,要先知道next值的作用是什么。
实际上主串第i个字符与模式串某个字符不匹配后,有两种不同的情况处理:
1.下次比较拿主串第i+1个字符与模式串第1个字符匹配;
2.下次比较依旧拿主串第i个字符与模式串的某个字符比较。
而next值的使用场景为:在KMP算法中,当主串与模式串逐个字符比较时,某个字符不匹配时,则模式串向右移动,移动的位数为next值+1。

首先next[0]的值固定为-1,而next[1]的值固定为0(关于这点后面会有解释)

KMP算法的next/nextval值的个人理解

从第j=2开始,看前面的字段有无两段相同的子串。此时前面字段为底色黄色的ab字段(以下情况的前面字段均以黄底标出)

KMP算法的next/nextval值的个人理解

很明显没有相同字段,故next[2]的值为0。这也能解释为什么t[1]的next值一定为0,毕竟t[1]前仅有t[0]一个数,根本不可能存在两段相同的子串,所以t[1]的next值必定为0。

j=3时同样在前面字段中没有两段相同字段,不再赘述。

当j=4时,如下图

KMP算法的next/nextval值的个人理解

可以看出前面字段abca中有两段相同的子串a,用红字标出,故相同字段的长度为1,则next值为1。(以下相同字段均以红字标出)

继续向下,当j=5时,情况与j=4相同。

当j=6时,如下图

KMP算法的next/nextval值的个人理解

可以看出此时前面字段中相同子串为ab,故相同字段长度为2,next值为2

接下来,当j=7时

KMP算法的next/nextval值的个人理解

可以看出此时前面字段中没有相同子串,故相同字段长度为0,next值为0但是,有些朋友看到这里会说,如果单纯找前面字段中的相同子串,那像刚刚j=6时的ab字段在这里也符合标准,为什么next值不为2呢?或者,像下面这张图片一样,为什么next值也不是1呢?

KMP算法的next/nextval值的个人理解

前缀子串和后缀子串

还记得上文提到的有约束条件子串吗?
这便是前缀子串后缀子串
前面的子串,叫前缀子串;同理,后面的子串,叫后缀子串

但关键在于,约束条件是什么呢?

让我们再观察一下刚刚那些没有问题子串,也就是前缀子串后缀子串

KMP算法的next/nextval值的个人理解

KMP算法的next/nextval值的个人理解

上面两张图中前缀子串和后缀子串有什么共同点呢?

可以发现,前缀子串第一位均为t[0]
若将此时j的值设为x后缀子串最后一位均为t[x-1]
用图形来理解,就是在黄底区域中,前缀子串的第一位必须是黄底区域的第一位,即t[0]
同样的,后缀子串的最后一位必须是黄底区域的最后一位,即t[x-1]

让我们回到j=7的情况中,在了解了前缀子串与后缀子串的定义之后,现在的你理解为什么next[7]=0了吗?

如果你理解了,那么恭喜你,真正掌握了next值的求算方法

观察模式串中的前缀子串和后缀子串,判断出的next值就是准确的。多加练习,就能很快求出next值。下面是完整的表图,大家可以对照着再练习一遍。

KMP算法的next/nextval值的个人理解

nextval值的求解

当你对next值的求解驾轻就熟之后,nextval值的求解相比之下就简单很多,除了nextval[0]的值仍为-1,其他nextval值都遵循以下规则

不同则同,同则等于

这是什么意思呢?

下面是题7的nextval值表

KMP算法的next/nextval值的个人理解

注意:上表为正确的表,下面例子中的表格中的j=7一栏中的next及nextval值错误,请以上图为准练习

我已经标出了所有数的nextval值,接下来让我们看几个例子:

当j=1时

KMP算法的next/nextval值的个人理解

t[1]=b,next[1]=0,则我们根据next[1]=0找到t[0]=a,a与b不同,则nextval[1]=next[1]=0,这就是不同则同

当j=2时

KMP算法的next/nextval值的个人理解

t[2]=c,next[2]=0,则我们根据next[2]=0找到t[0]=a,a与c不同,则nextval[2]=next[2]=0

当j=3时

KMP算法的next/nextval值的个人理解

t[3]=a,next[3]=0,则我们根据next[3]=0找到t[0]=a,a与a相同,则nextval[3]=nextval[0]=-1,这就是同则相等,即两字符相同时两者的nextval值相等

接下来的nextval值判断同样遵循以上方法,大家可以自己试着练习一下

注意:第一个表为正确的表,例子中的表格中的j=7一栏中的next及nextval值错误,请以第一个图为准练习

使用上面的方法可以比较容易地得到next值与nextval值,希望可以帮助到大家的计算以及对KMP算法的理解。

发表评论

:?: :razz: :sad: :evil: :!: :smile: :oops: :grin: :eek: :shock: :???: :cool: :lol: :mad: :twisted: :roll: :wink: :idea: :arrow: :neutral: :cry: :mrgreen: