KMP算法以及优化(代码分析以及求解next数组和nextval数组)

来了,数据结构及算法的内容来了,这才是我们的专攻,前面写的都是开胃小菜,本篇文章,侧重考研408方向,所以保证了你只要看懂了,题一定会做,难道这样思想还会不会么?如果只想看next数组以及nextval数组的求解可以直接跳到相应部分,思想总结的很干~~

网上的next数组版本解惑

先总结一下,一般KMP算法的next数组结果有两个版本,我们需要知道为什么会存在这种问题,其实就是前缀和后缀没有匹配的时候next数组为0还是为1,两个版本当然都是对的了,如果next数组为0是的版本,那么对于前缀和后缀的最大匹配长度只需要值+1就跟next数组是1的版本一样了,其实是因为他们的源代码不一样,或者对于模式串的第一个下标理解为0或者1,总之这个问题不用纠结,懂原理就行~~

那么此处,我们假定前缀和后缀的最大匹配长度为0时,next数组值为1的版本,考研一般都是用这个版本(如果为0版本,所有的内容-1即可,如你算出next[5]=6,那么-1版本的next[5]就为5,反之亦然)~~

其实上面的话总结就是一句话

next[1]=0,j(模式串)数组的第一位下标为1,同时,前缀和后缀的最大匹配长度+1即为next数组的值,j所代表的的是序号的意思

408反人类,一般数组第一位下标为1,关于书本上前面链表的学习大家就应该有目共睹了,书本上好多数组的第一位下标为了方便我们理解下标为1,想法这样我们更不好理解了,很反人类,所以这里给出next[1]=0,前缀和后缀的最大匹配长度+1的版本讲解

前言以及问题引出

我们先要知道,KMP算法是用于字符串匹配的~~

例如:一个主串”abababcdef”我们想要知道在其中是否包括一个模式串”ababc”

初代的解决方法是,朴素模式匹配算法,也就是我们主串和模式串对比,不同主串就往前移一位,从下一位开始再和模式串对比,每次只移动一位,这样会很慢,所以就有三位大神一起搞了个算法,也就是我们现在所称的KMP算法~~

代码以及理解

源码这里给出~~

int Index_KMP(SString S,SString T,intt next[]){
    int i = 1,j = 1;//数组第一位下标为1
    while (i &lt;= S.length &amp;&amp; j &lt;= T.length){
        if (j == 0 || S.ch[i] == T.ch[j]){//数组第一位下标为1,0的意思为数组第一位的前面,此时++1,则指向数组的第一位元素
            ++i;
            ++j;//继续比较后继字符
        }
        else
            j = next[j];//模式串向右移动到第几个下标,序号(第一位从1开始)
    }
    if (j &gt; T.length)
        return i - T.length;//匹配成功
    else
        return 0;}

接下来就可以跟我来理解这个代码~~

还不会做动图,这里就手画了~~

以上是一般情况,那么如何理解j=next[1]=0的时候呢?

是的,这就是代码的思路,那么这时我们就知道,核心就是要求next数组各个的值,对吧,一般也就是考我们next数组的值为多少~~

next数组的求解

这里先需要给出概念,串的前缀以及串的后缀~~

串的前缀:包含第一个字符,且不包含最后一个字符的子串

串的后缀:包含最后一个字符,且不包含第一个字符的子串

当第j个字符匹配失败,由前1~j-1个字符组成的串记为S,则:next[j]=S的最长相等前后缀长度+1

与此同时,next[1]=0

如,模式串”ababaa”

序号J	1	2	3	4	5	6
模式串	a	b	a	b	a	a
next[j]	0

当第六个字符串匹配失败,那么我们需要在前5个字符组成的串S”ababa”中找最长相等的前后缀长度为多少再+1~~

如串S的前缀可以为:”a”,”ab”,”aba”,”abab”,前缀只不包括最后一位都可

串S的后缀可以为:”a”,”ba”,”aba”,”baba”,后缀只不包括第一位都可

所以这里最大匹配串就是”aba”长度为3,那么我们+1,取4

序号J	1	2	3	4	5	6
模式串	a	b	a	b	a	a
next[j]	0					4

再比如,当第二个字符串匹配失败,由前1个字符组成的串S”a”中,我们知道前缀应当没有,后缀应当没有,所以最大匹配串应该为0,那么+1就是取1~~

其实这里我们就能知道一个规律了,next[1]一定为0(源码所造成),next[2]一定为1(必定没有最大匹配串造成)~~

序号J	1	2	3	4	5	6
模式串	a	b	a	b	a	a
next[j]	0	1				4

再再比如,第三个字符串匹配失败,由前两个字符组成的串S”ab”中找最长相等的前后缀长度,之后再+1~~

前缀:”a”

后缀:”b”

所以所以这里最大匹配串也是没有的长度为0,那么我们+1,取1

序号J	1	2	3	4	5	6
模式串	a	b	a	b	a	a
next[j]	0	1	1			4

接下来你可以自己练练4和5的情况~~

这里直接给出答案~~

序号J	1	2	3	4	5	6
模式串	a	b	a	b	a	a
next[j]	0	1	1	2	3	4

是不是很简单呢?

至此,next数组的求法以及kmp代码的理解就ok了~~

那么接下来,在了解以上之后,我们想一想KMP算法存在的问题~~

KMP算法存在的问题

如下

主串:”abcababaa”

模式串:”ababaa”

例如这个问题

我们很容易能求出next数组

序号J	1	2	3	4	5	6
模式串	a	b	a	b	a	a
next[j]	0	1	1	2	3	4

此时我们是第三个字符串匹配失败,所以我们的next[3]=1,也就是下次就是第一个字符”a”和主串中第三个字符”c”对比,可是我们刚开始的时候就已经知道模式串的第三个字符”a”和”c”不匹配,那么这里不就多了一步无意义的匹配了么?所以我们就会有kmp算法的一个优化了~~

KMP算法的优化

我们知道,模式串第三个字符”a”不和主串第三个字符”c”不匹配,next数组需要我们的next[3]=1,也就是下次就是第一个字符”a”和主串中第三个字符”c”对比,之后就是模式串第一个字符”a”不和”c”匹配,就是需要变为next[1]=0,那么我们要省去步骤,不就可以直接让next[3]=0么?

序号J	1	2	3	4	5
模式串	a	b	a	b	a
next[j]	0	1	1	2	3
nextval[j]	0		0

那么怎么省去多余的步骤呢?

这就是nextval数组的求法~~

nextval的求法以及代码理解

先贴出代码

for (int j = 2;j &lt;= T.length;j++){
if (T.ch[next[j]] == T.ch[j])
        nextval[j] = nextval[next[j]];
    else
        nextval[j] = next[j];
}

如

序号J	1	2	3	4	5	6
模式串	a	b	a	b	a	a
next[j]	0	1	1	2	3	4
nextval[j]	0

首先,第一次for循环,j=2,当前序号b的next[2]为1,即第一个序号所指向的字符a,a!=当前序号b,所以nextval[2]保持不变等于next[2]=1

序号J	1	2	3	4	5	6
模式串	a	b	a	b	a	a
next[j]	0	1	1	2	3	4
nextval[j]	0	1

第二次for循环,j=3,当前序号a的next[3]为1,即第一个序号所指向的字符a,a=当前序号a,所以nextval[3]等于nextval[1]=0

序号J	1	2	3	4	5	6
模式串	a	b	a	b	a	a
next[j]	0	1	1	2	3	4
nextval[j]	0	1	0

第三次for循环,j=4,当前序号b的next[4]为2,即第二个序号所指向的字符b,b=当前序号b,所以nextval[4]等于nextval[2]=1

序号J	1	2	3	4	5	6
模式串	a	b	a	b	a	a
next[j]	0	1	1	2	3	4
nextval[j]	0	1	0	1

就是这样,你可以练练5和6,这里直接给出~~

序号J	1	2	3	4	5	6
模式串	a	b	a	b	a	a
next[j]	0	1	1	2	3	4
nextval[j]	0	1	0	1	0	4

至此nextval数组的求法你也应该会了,那么考研要是考了,那么是不是就等于送分给你呢?

小练习

那么你试着来求一下这个模式串的next和nextval数组吧~~

模式串:”aaaab”

序号j	1	2	3	4	5
模式串	a	a	a	a	b
next[j]
nextval[j]

小练习的答案

序号j	1	2	3	4	5
模式串	a	a	a	a	b
next[j]	0	1	2	3	4
nextval[j]	0	0	0	0	4