KMP前缀表直觉

Question

正如我所见（在所有在线资源中，甚至在这个答案中），在 KMP 中构建故障/前缀表的主要函数如下：

int j = 0;  
    for (int i = 1; i < pattern.length(); i++) {  
      while (j > 0 && pattern.charAt(j) != pattern.charAt(i)) {   
        j = failure[j - 1];  
      }  
      if (pattern.charAt(j) == pattern.charAt(i)) {   
        j++;   
      }  
      failure[i] = j;  
    }

我无法理解这部分：
j = failure[j - 1];

为什么我们不j--返回字符串呢？j我们如何知道使用失败的表进行更新是正确的？

Answer 1

如果失败表的第 i 个条目是长度为 i 的模式的前缀的最长后缀-前缀匹配的长度，则 KMP 字符串匹配正确。

请注意，如果A[0..k]是 的后缀-前缀匹配A[0..i]，则A[0..k]是 的最长后缀-前缀匹配A[0..i]，或者是所述最长后缀-前缀匹配的后缀-前缀匹配。

当你把这两件事放在一起时，结果表明我们想要的failure[i]是 的最长后缀-前缀匹配的长度pattern[0..i]。KMP 预处理failure使用以下事实进行归纳构建：

如果 的最长后缀-前缀匹配A[0..i]非空，则砍掉最后一个字符将给出 的一些后缀-前缀匹配A[0..i-1]。

因此， 的最长后缀-前缀匹配A[0..i]要么为空，要么通过将 的最长后缀-前缀匹配扩展A[0..i-1]一个字符或通过将该最长后缀-前缀匹配的后缀-前缀匹配扩展一个字符而形成。前面字符的失败函数为您提供了一种迭代 的所有后缀-前缀匹配的简单方法pattern[0..i-1]。