对KMP算法中next数组的抽象理解

标签: 笔记

最近考研复习看数据结构,发现KMP算法并不是那么简单。在KMP算法中,最关键的地方就是Next数组的获得。
刚开始学的时候看getnext()函数的代码,感觉跟着程序推很难理解,尤其是那个j=next[j]。然后就尝试着抽象地去理解了一下,发现效果不错。
思路大概是这样的:

这里写图片描述

图中的绿色部分是主串和子串匹配的部分(图中只花了三个方块但实际个数不限),在第四个方块处,发生了不匹配,这个时候的状态为Sk,我们要让它往Sk+1走,就要让子串的下标j通过 j=next[j] 这条语句进行迭代。那么,问题的关键就是怎么样找到要移动到的那个新下标next[j]。

这里写图片描述
把子串和主串匹配的部分拿出来分析,图中蓝色部分是匹配部分的最后一个字符,红色部分是蓝色部分表示的字符前的字符串中的最大前后缀,若此时最大前缀的后一个字符,即图中 ? 的那个方块和蓝色部分的字符一样,则前缀和前缀后一字符可以对后缀与后缀后一个字符进行替换,此时有next[j] = t + 1。

那如果红色前缀后的字符和蓝色部分表示的字符不等呢?

这里写图片描述

当?所指字符与蓝色部分字符不相等的时候,把红色前缀放大来看,如果红色前缀有最大前后缀,如图中黄色区域所示,且??所指字符与蓝色部分字符相等,那么这时候有next[j] = t1 + 1 。如果按这样下去,一直不匹配直到没有最大前后缀,子串就不能平移了,这个时候有next [j] = 1。

根据上面的思考容易想到,在代码方面,next[j+1]是可以由next[i<=j]推出来的,这样理解起来就比较舒服了。

以上就是我不成熟的理解,写着整理下思路,方便以后复习用,若有错误欢迎指正。

附代码:

/*__author__ hui 
  __time__ 18/8/21
*/
#include <iostream>
#include <string.h>

using namespace std;

void get_next(char* Sub_string,int *next)
{
    int lenth = strlen(Sub_string);
    int i=1,j=0;
    next[1]=0;
    while(i<lenth)
    {
        if(j==0 || Sub_string[i] == Sub_string[j])
        {
            i++;
            j++;
            next[i]=j; 
        }
        else
            j = next[j];
    }
}

int KMP(char * string , char * Sub_string, int * next)
{
    int i = 1,j = 1;
    int lenth = strlen(string);
    int sub_lenth = strlen(Sub_string);
    while(i<=lenth&&j<=sub_lenth)
    {
        if(j==0 || string[i-1]==Sub_string[j-1])
        {
            /*
            if (j==sub_lenth)
                break;
                这条不用加因为如果最后一个字符也匹配的话,会进入循环然后由 j<sub_string[j] 这一条件跳出 
                */   
            i++;
            j++;

        }
        else 
            j=next[j];
    }
    if(j>sub_lenth)
    {
        return i-sub_lenth;
    }
    else 
        return 0;
}

int main(int argc, char** argv) {

    char* string = "nmslnmssnmsl";
    char* sub_string = "nmss";
    int sub_lenth = strlen(sub_string);
    int flag;
    int* next = new int(sub_lenth+1);
    get_next(sub_string,next);
    flag = KMP(string,sub_string,next);
    if (flag!=0)
    {
        cout<<"在主串的第"<<flag<<"个字符发生匹配" ;
    }
    else
        cout<<"没有匹配字符" ;

    delete[] next;
    return 0;
}

9/16
补充:
关于nextval数组,思路是如果当前失配的next的值与当前值相同,则这次next迭代的结果也必将失配,让nextval[i] = nextval[next[i]](注:因为get_next是从i=1向上获取的,因此不用考虑next[i]项 与next[next[i]]项相等的情况,因为如果相等在nextval数组中是会被跳过的,nextval就直接到了不等的那个值 )。如果当前失配值与next的值不同,则让他为next即可。

版权声明:本文为qq_38758395原创文章,遵循 CC 4.0 BY-SA 版权协议,转载请附上原文出处链接和本声明。
本文链接:https://blog.csdn.net/qq_38758395/article/details/81714603