rt，前者是一个 SPJ 里抄的是类 KMP，后者是标准 KMP 的 next 数组的计算方式，相关（类 KMP 的）题面如下：

next数组是KMP算法的核心。对于长度为N的字符串S，我们可以计算出一个长度同样为 N 的 next 数组，其中next[i]代表S[0…i]这个子串（包含第0个与第i个字符）的最长公共非平凡前后缀长度，也即，next[i]= 所有满足S[0…j]= S[i-j…i] 的j中的最大的那个j。

题面有明确标注其不为 KMP 算法，两段代码如下：

void calc_next_onestep(const string &s, int result[], int pos) {
    if (pos == 0) {
        result[0] = 0;
        return;
    }
    int p = result[pos-1];
    while (p && s[p] != s[pos]) p = result[p-1];
    result[pos] = p + (s[p] == s[pos]);
}

void calc_next(const string &s, int result[]) {
    const int n = s.length();
    assert(n);
    result[0] = 0;
    if (n == 1) return;
    result[1] = s[0] == s[1];
    for (int i = 2; i < n; ++i) {
        calc_next_onestep(s, result, i);
    }
}

	nxt[0]=nxt[1]=0;
	for(int i=2,j=0;i<=n;i++)
	{
		while(j&&str[i]^str[j+1]) j=nxt[j];
		if(str[i]==str[j+1]) nxt[i]=++j;
	}