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

这里是进阶，所以如果有小伙伴不知道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++的代码均经过调试，大家可放心使用。