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 = 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]的所有后缀-前缀匹配。

Answer 2

这个视频确实有助于我们清楚地理解为什么我们需要做j= failurej - 1；而不是j--；

https://www.youtube.com/watch?v=tWDUjkMv6Lc&feature=emb_logo