当前位置:   article > 正文

KMP算法,字符串匹配,next与nextval数组求解_nextvel数组

nextvel数组

KMP算法简介

KMP算法是一种改进的字符串匹配算法,其核心是利用匹配失败后的信息,尽量减少模式串与主串的匹配次数以达到快速匹配的目的。换句话说就是KMP算法解决了传统字符串匹配过程中主串指针回溯的问题,那么它是如何实现的呢?主要利用的是前缀表,即next数组。

next数组手动求解过程

首先声明,next数组针对的是模式串(即需要从主串中寻找出来的目标字符串)而非主串,下面通过一个事例来说明next数组求解过程。

目标模式串str为:abaababa

strabaababa
下标01234567
next-1

我的习惯是next[0]初始化为-1(因为下标从0开始),也有其他说法next[0]初始化为0,其实本质上是一致的,只不过在代码实现上略有差异。

next[i]的数值是第i项前面字串的最长公共前后缀长度(不包括字串它本身),深入理解这句话也就弄懂了KMP算法。接下来动手依次求解事例的next[1]至next[7]。

next[1]:str[1]b之前的字串为a,最长公共前后缀长度为0(a自身不算),所以next[1]=0;

next[2]:str[2]a之前的字串为ab,最长公共前后缀长度为0(ab自身不算),所以next[2]=0;

next[3]:str[3]a之前的字串为aba,最长公共前后缀为a,长度为1,所以next[3]=1;

next[4]:str[4]b之前的字串为abaa,最长公共前后缀为a,长度为1,所以next[4]=1;

next[5]:str[5]a之前的字串为abaab,最长公共前后缀为ab,长度为2,所以next[5]=2;

next[6]:str[6]b之前的字串为abaaba,最长公共前后缀为aba,长度为3,所以next[6]=3;

next[7]:str[7]a之前的字串为abaabab,最长公共前后缀为ab,长度为2,所以next[7]=2;

所以最终事例的next数组如下

strabaababa
下标01234567
next-10011232

求出next数组后出现疑惑了,next数组有什么意义呢?其各数值又代表着什么呢?

next[i]数组的值意义如下:进行字符串匹配时,当模式串与主串不匹配的时候,其next数组的值决定了模式串应该从哪里开始重新匹配,而主串指针无需回溯,这就是KMP算法的优势。

比如:假设例子中与模式串进行匹配的主串为:abaabaababab

请添加图片描述
str[6]=b,next[6]=3,模式串指针回退至下标3重新匹配,最终匹配成功,方框中的内容一定的匹配的(公共前后缀)!!!(因为不会做动画只能用图片描述了,敬请谅解)

由事例匹配情况发现,匹配过程中主串指针并未回溯,因此极大地提高了字符串匹配效率。

next数组求解(代码实现)

// 代码部分
void getNext(char*str,int*next)
{
	int i,j,len;
	i=0;
	j=-1;
	next[0]=-1;
	len=strlen(str);
	while(i<len-1)
	{
		if(j==-1||str[i]==str[j])
		{
			++i;
			++j;
			next[i]=j;
		}else
		{
			j=next[j];
		}
	}
}
  • 1
  • 2
  • 3
  • 4
  • 5
  • 6
  • 7
  • 8
  • 9
  • 10
  • 11
  • 12
  • 13
  • 14
  • 15
  • 16
  • 17
  • 18
  • 19
  • 20
  • 21

至于next数组的代码实现,手动模拟执行代码,仔细体会,多敲几遍就好,重点在于手动求取next数组并理解其含义。

改进的KMP算法

至于改进的KMP算法,主要是涉及到nextval数组,它进一步优化了KMP算法。那么它是如何优化的呢?

手动求解nextval数组

如果要求解nextval数组,则必须先求解next数组,还是以事例来举例。
目标模式串为:abaababa

strabaababa
下标01234567
next-10011232
nextval-1

将nextval[0]初始化为-1;
求解nextval数组的过程是,将str[i]与str[next[i]]进行比较,如果不同则nextval[i]=next[i],如果相同则nextval[i]=nextval[next[i]],下面依次求解nextval[1]至nextval[7]。
nextval[1]:str[1]=‘b’,str[next[1]]=str[0]=‘a’,不同,所以nextval[1]=next[1]=0;
nextval[2]:str[2]=‘a’,str[next[2]]=str[0]=‘a’,相同,所以nextval[2]=nextval[next[2]]=-1;
nextval[3]:str[3]=‘a’,str[next[3]]=str[1]=‘b’,不同,所以nextval[3]=next[3]=1;
nextval[4]:str[4]=‘b’,str[next[4]]=str[1]=‘b’,相同,所以nextval[4]=nextval[next[4]]=0;
nextval[5]:str[5]=‘a’,str[next[5]]=str[2]=‘a’,相同,所以nextval[5]=nextval[next[5]]=-1;
nextval[6]:str[6]=‘b’,str[next[6]]=str[3]=‘a’,不同,所以nextval[6]=next[6]=3;
nextval[7]:str[7]=‘a’,str[next[7]]=str[2]=‘a’,相同,所以nextval[7]=nextval[next[7]]=-1;

所以nextval数组如下:

strabaababa
下标01234567
next-10011232
nextval-10-110-13-1

至于为什么nextval要这么求,我的理解如下:因为nextval代表的是匹配错误时模式串从什么位置重新开始匹配,由此当匹配错误时,如果str[i]=str[next[i]],说明模式串指针移动至next[i]处并不能使其匹配成功,因为str[i]与str[next[i]]是一致的且str[i]匹配错误,所以nextval[i]直接取nextval[next[i]]。这也正是KMP算法的改进之处。

nextval数组求解(代码实现)

void getnextval(char* str,int* nextval)
{
    int i,j,len;
    i=0;
    j=-1;
    len=strlen(str);
    nextval[0]=-1;
    while (i < len - 1)
    {
        if (j == -1 || str[i] == str[j])
        {
            ++i;
            ++j;
            if (str[i] == str[j])
            {
                nextval[i] = nextval[j];
            }
            else
            {
                nextval[i] = j;
            }
        }
        else
        {
            j = nextval[j];
        }
    }
}
  • 1
  • 2
  • 3
  • 4
  • 5
  • 6
  • 7
  • 8
  • 9
  • 10
  • 11
  • 12
  • 13
  • 14
  • 15
  • 16
  • 17
  • 18
  • 19
  • 20
  • 21
  • 22
  • 23
  • 24
  • 25
  • 26
  • 27
  • 28

求解代码,自己手动模拟执行,多敲几遍达到熟练就行。

next[i]=-1与nextval[i]=-1的意义是主串指针右移一位,模式串指针回到首部(下标0)。

发表本文的目的主要是做一下笔记,因为过了一段时间老是会忘,记录一下知识点,第一次写这么长的博客,如果有错误欢迎大家在评论区告诉我,谢谢大家!

声明:本文内容由网友自发贡献,不代表【wpsshop博客】立场,版权归原作者所有,本站不承担相应法律责任。如您发现有侵权的内容,请联系我们。转载请注明出处:https://www.wpsshop.cn/w/木道寻08/article/detail/832287
推荐阅读
相关标签
  

闽ICP备14008679号