如何理解kmp的next数组

Question

这里t是要查找的子串，m是t串的长度。请问下kmp算法中next数组的含义是什么，以及下面这段代码的求法是否正确。

void getNext()
{
    nxt[0] = 0;
    int j = 0, i = 1;
    while (i < m)
    {
        if (t[j] == t[i])
        {
            nxt[i] = ++j;
            i++;
        }
        else if (j == 0)
        {
            nxt[i] = 0;
            i++;
        }
        else
        {
            j = nxt[j - 1];
        }
    }
}
//KMP算法是一种改进的字符串匹配算法，由D.E.Knuth，J.H.Morris和V.R.Pratt提出的，因此人们称它为克努特—莫里斯—普拉特操作（简称KMP算法）。KMP算法的核心是利用匹配失败后的信息，尽量减少模式串与主串的匹配次数以达到快速匹配的目的。具体实现就是通过一个next()函数实现，函数本身包含了模式串的局部匹配信息。KMP算法的时间复杂度O(m+n)

Answer 1

可以参考这里

软考笔记（数据结构篇）———— KMP算法_岁月可贵的博客-CSDN博客_软考kmp算法题 KMP 算法主串P： a b a c b c a b a b a b b c b c模式串S：a b a c b c a第一步：计算模式串S的前缀码规则: 前后缀码必须一致且是最长，不能超过模式串本身。第二步：列好表格进行匹配，如下：比较开始：从模式串S[0] 和主串P[0]，开始匹配，相同。则 i++，j++；直到不匹配。第一遍匹配到：S[3] 不等于 P[3]此时找到模式串S[3]对应的next 值为 1，主串匹配位不变，模式串移动到 S[1]（即字符串b）此时还是不等 https://blog.csdn.net/weixin_44659458/article/details/122850360