对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即可。