4

如我所见，在 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使用失败的表进行更新是正确的？

4

2 回答 2

3

如果故障表的第 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].

于 2012-12-12T18:19:09.167 回答
1

这个视频真的有助于让直觉清楚为什么我们需要做 j = failure[j - 1]; 而不是 j--;

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

于 2021-02-06T19:41:22.647 回答