string - KMP 前缀表直觉

Question

如我所见，在 KMP 中构建故障/前缀表的主要函数(在所有在线资源中，甚至在这个 answer _ 中，如下所示:

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 = 失败[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 预处理使用以下事实归纳地构建失败:

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

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