algorithm - 计算 KMP 实现中的下一个前缀索引

Question

我已经阅读了许多不同的 KMP 实现，并不能完全弄清楚它们都共享的一个方面。

当他们计算也是后缀数组（lps）的最长前缀时。如果字符在特定迭代中测试的索引处不匹配，并且前缀的索引不为0。前缀的索引设置为

索引 = lps[索引 - 1];

这是一个例子

void computeLPSArray(String pat, int M, int lps[])
{
    // length of the previous longest prefix suffix
    int len = 0;
    int i = 1;
    lps[0] = 0;  // lps[0] is always 0

    // the loop calculates lps[i] for i = 1 to M-1
    while (i < M)
    {
        if (pat.charAt(i) == pat.charAt(len))
        {
            len++;
            lps[i] = len;
            i++;
        }
        else  // (pat[i] != pat[len])
        {
            // This is tricky. Consider the example.
            // AAACAAAA and i = 7. The idea is similar 
            // to search step.
            if (len != 0)
            {
                len = lps[len-1];

                // Also, note that we do not increment
                // i here
            }
            else  // if (len == 0)
            {
                lps[i] = len;
                i++;
            }
        }
    }
}

是否存在index = lps[index-1]不等于的情况

指数 - ;