【进阶KMP算法】nextval手算代码均有详解(每步配图)

2024-01-01 19:29:37

这里是进阶,所以如果有小伙伴不知道KMP算法是什么的话,请看上一章(写的很清楚),故我这里概念什么的就不再过多描述。

引入:

要改进那么肯定要知道,哪里有不足,我们假设目标串s为“aaabaaaab”,模式串t为"aaaab",模式串t对应的next数组如下面的图所示。


?KMP算法比较图大家看看就会发现哪里能改进

由于图比较长所以我分成几份发,最后有一个总的如果可以保存的话大家直接看最后一个就行。


总图片


我们发现一共需要12次字符比较,我们看到t[0]t[1]t[2]t[3]这几个字符相同,所以如果t[3]不行,那么t0,1,2是不是都没有比较的意义了,这里就是我们能改进的。

改进主要体现在next数组的求解中

改进:nextval

我先给出代码,大家看看和next数组有什么不同的地方

void GetNextval(char*t,int nextval[])
{
    int j=0,k=-1;
    int length = strlen(t);
    nextval[0] = -1;
    while(j<length-1)
    {
        if(k==-1||t[j]==t[k])
        {
            j++;k++;
            if(t[j]!=t[k])
            {
                nextval[j] = k;
            }
            else nextval[j] = nextval[k];
        }
        else k = nextval[k];
    }
}

我们发现,是在while里面多了if判断语句,这个就是来实现,上面图中要改进的地方。如果不知道next数组怎么求还是先看看我前面写的文章,nextval是基于next数组来写的。大家可以好好理解一下。

下面我讲讲nextval怎么手算(可以用来考试)

总结出来就一句话(相同用下面,不同用next)

详解:红色为重点要看的

首先看next【2】为0,接着看t【0】和t【2】(因为此时不同点在2)相同故nextval【2】用下面nextval【0】=-1,如果不相同直接用上面的next【2】=0.下面的类似。


因为t【5】!=t【3】所以nextval【5】 = next【5】 = 3.

下面我给出一个t数组大家算算next和nextval看看掌握了没有,答案后面给出

手算例题

答案:

大家一定要先自己写完再看答案。

总代码

c++

//改进的KMP算法
#include "sqstring.cpp"
void GetNextval(SqString t,int nextval[])  //由模式串t求出nextval值
{
	int j=0,k=-1;
	nextval[0]=-1;
   	while (j<t.length) 
	{
       	if (k==-1 || t.data[j]==t.data[k]) 
		{	
			j++;k++;
			if (t.data[j]!=t.data[k]) 
				nextval[j]=k;
           	else  
				nextval[j]=nextval[k];
       	}
       	else  k=nextval[k];    	
	}

}
int KMPIndex1(SqString s,SqString t)    //修正的KMP算法
{
	int nextval[MaxSize],i=0,j=0;
	GetNextval(t,nextval);
	while (i<s.length && j<t.length) 
	{
		if (j==-1 || s.data[i]==t.data[j]) 
		{	
			i++;j++;	
		}
		else j=nextval[j];
	}
	if (j>=t.length)  
		return(i-t.length);
	else
		return(-1);
}
int main()
{
	SqString s,t;
	StrAssign(s,"ababcabcacbab");
	StrAssign(t,"abcac");
	printf("s:");DispStr(s);
	printf("t:");DispStr(t);
	printf("位置:%d\n",KMPIndex1(s,t));
	return 1;
}

c语言

#define  _CRT_SECURE_NO_WARNINGS 1
#include <stdio.h>
#include <string.h>
#include <stdlib.h>
void GetNextval(char* t, int nextval[])
{
    int j = 0, k = -1;
    int length = strlen(t);
    nextval[0] = -1;
    while (j < length - 1)
    {
        if (k == -1 || t[j] == t[k])
        {
            j++; k++;
            if (t[j] != t[k])
            {
                nextval[j] = k;
            }
            else nextval[j] = nextval[k];
        }
        else k = nextval[k];
    }
}
int KMPIndex(char* haystack, char* needle) {
    int i = 0, j = 0;
    int length1 = strlen(haystack);
    int length2 = strlen(needle);
    int nextval[100];//可变
    GetNextval(needle, nextval);
    while (i < length1 && j < length2)
    {
        if (j == -1 || haystack[i] == needle[j])
        {
            i++; j++;
        }
        else j = nextval[j];
    }
    if (j >= length2) return i - length2;
    else return -1;
}
int main()
{
    char str1[] = "aaabaaaab";
    char str2[] = "aaaab";
    int k = KMPIndex(str1, str2);
    printf("%d", k);
    return 0;
}

上面给出的c语言和c++的代码均经过调试,大家可放心使用。

例题力扣例题28(推荐BF和KMP算法都用一下,特别是KMP)

结语:

其实写博客不仅仅是为了教大家,同时这也有利于我巩固自己的知识点,和一个学习的总结,对文章有任何问题的还请指出,接受大家的批评,让我改进,如果大家有所收获的话还请不要吝啬你们的点赞和收藏,这可以激励我写出更加优秀的文章。

文章来源:https://blog.csdn.net/2301_80035594/article/details/135326229
本文来自互联网用户投稿,该文观点仅代表作者本人,不代表本站立场。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。