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

博主： ZaunEkko
发布时间：2021 年 05 月 24 日
9896次浏览
1 条评论
1047字数
分类：数据结构

# 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算法~~

## 代码以及理解

源码这里给出~~

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

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

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

![img](https://www.zaunekko.com/download/image/kmp/1.jpg)

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

![img](https://www.zaunekko.com/download/image/kmp/2.jpg)

是的,这就是代码的思路,那么这时我们就知道,核心就是要求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数组

此时我们是第三个字符串匹配失败,所以我们的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的求法以及代码理解

先贴出代码

```c
for (int j = 2;j <= 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    |

最后修改：2021 年 06 月 02 日 02 : 42 PM

END

本文作者： ZaunEkko
文章标题：KMP算法以及优化(代码分析以及求解next数组和nextval数组)
本文地址：https://www.zaunekko.com/archives/13/
版权说明：若无注明，本文皆ZaunEkko原创，转载请保留文章出处。

如果觉得我的文章对你有用，请随意赞赏

1 条评论

在下YB Google Chrome 91.0.4472.77 Windows 10
June 3rd, 2021 at 06:43 pm

ddd滴！学生卡！打卡时间：下午6:43:31，请上车的乘客系好安全带~

回复

发表评论取消回复

评论 *

私密评论

名称 *

🎲

邮箱 *

地址

鬼鬼
你评论的时候有没有报错啊
书签网
这张图片很不错
笒鬼鬼
你的文章大图版怎么是这样的，怎么修改的可以分享下？css
笒鬼鬼
站点名称：笒鬼鬼站点链接：https://www.cengui...
笒鬼鬼
站点名称：笒鬼鬼站点链接：https://www.cengui...

今日已经过去小时

这周已经过去天

本月已经过去天

今年已经过去个月

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

ZaunEkko • 2021 年 05 月 24 日

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

## 网上的next数组版本解惑

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

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

## 前言以及问题引出

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

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

## 代码以及理解

源码这里给出~~

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

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

![img](https://www.zaunekko.com/download/image/kmp/1.jpg)

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

![img](https://www.zaunekko.com/download/image/kmp/2.jpg)

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

## next数组的求解

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

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

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

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

与此同时,next[1]=0

如,模式串"ababaa"

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

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

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

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

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

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

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

前缀:"a"

后缀:"b"

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

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

这里直接给出答案~~

是不是很简单呢?

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

---

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

## KMP算法存在的问题

如下

主串:"abcababaa"

模式串:"ababaa"

例如这个问题

我们很容易能求出next数组

## KMP算法的优化

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

这就是nextval数组的求法~~

## nextval的求法以及代码理解

先贴出代码

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

如

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

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

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

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

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

---

## 小练习

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

模式串:"aaaab"

---

小练习的答案

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

1 条评论

发表评论取消回复

个人博客同步

VSCode配置MSVC+VSCode使用easyx库,2021.5.13日配置~~

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

RSA加密算法,针对考试,必拿分

最小生成树,Prim算法与Kruskal算法,408方向,思路与实现分析

MarkDown学习

生病了

最小生成树,Prim算法与Kruskal算法,408方向,思路与实现分析

网络工程实验安排

C++PRIMER第五版练习题答案第一章

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

1 条评论

发表评论 取消回复

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

发表评论取消回复