KMP next数组的理解问题

Question

void GetNext(char* p int *next)
{
    int pLen = strlen(p); //求出长度;
    next[0] = -1;
    int k = -1;
    int j = 0;
    while (j < pLen - 1)
    {
        //p[k]表示前缀，p[j]表示后缀
        if (k == -1 || p[j] == p[k])   //匹配时,
        {
            ++k;
            ++j;
            next[j] = k;
        }
        else  //不匹配时;
        {
            k = next[k];//不满足就后退;
        }
    }
}

今天在基本了解KMP算法后大致明白了它的原理，以及next[]数组的求法，
满足一下规律它如果有相同最长的前后缀则位前缀的下一位，如果没有前后缀则为当前位 ，我对代码next[j]=k的理解 ，就是满足在p[i]=p[k] 的情况下的 将其当作最长前串存它的下一位 ,而k=next[k] ,就是当没有相同的最长前后缀时 返回到上一个有相同前后缀的位置，在对其进行比较加长。
这段代码是如何求出在不匹配时的当前位呢？
比如
A B A B
0 1 1 2
它的 匹配到B时返回到 1 上述的求next[]数组是如何做到的呢？
感觉上述的代码在没有相同的前后缀的情况下都会退回到 ,k=-1 , next[j]=0 ;希望大佬能指点一下.

Answer 1

按你的代码，你提供的

A B A B  
0 1 1 2

是错的，应该是，

 A B A B  
-1 0 0 1

next 数组是用来失配时进行跳转的，既然你都理解了 next 数组是如何求解的，那我觉得也应该能理解这点啊。KMP 算法难点是如何求解 next 数组，而不是如何理解 next 数组的作用，你倒是反过来了。

我直接丢一篇文章：https://ethsonliu.com/2018/04...