KMP模式查找算法

Question

我确实理解了KMP算法，即存储值以匹配前缀，然后在字符串中搜索时不返回，因为模式"abcdabca“前缀数组将是{0,0,0,0,1,2,3,1}，直到{0，0，0，0，0，2，3，3，}，然后'd‘在第4位置与'a’不匹配。然后，algo说回到arrj-1，如果j!=0，我可以看到这给了我们正确的结果，但我不明白为什么我们要返回到以前的元素数据作为理解的基础。

我们回去直到找到匹配的元素或j==0，我想不出一个方法来理解为什么我们要回去。

谢谢

Answer 1

根据我自己的理解，我们使用failure函数F[i]来表示最长前缀的基于0的索引，该索引与子字符串S[0...i]的后缀相同(最长，指的是整个子字符串本身以外最长的)。

从您的操作中，我认为您的实现或教程使用的是基于1的，但这完全取决于实现

考虑以下示例：S = abababcabab

故障函数将类似于F = [-1,-1,0,1,2,3,-1,0,1,2,3]

您可以仔细观察的是，当算法在完成对S' = ababab????和F = [-1,-1,0,1,2,3,?,?,?,?,?]的故障函数计算时发生了什么

现在下一个字符是c，算法将测试它是否可以附加到已知最长的前缀(后缀) abab上，以使其更长。测试作为前缀ababa !=后缀ababc失败，但是接下来呢？

然后，算法将尝试查看失败的最长前缀(后缀)最长前缀(后缀)，并查看挂起一个c会给我们一个匹配(如果是，那么它就是答案)。

这意味着该算法将测试 abab的最长前缀(后缀)，即ab，因为我们知道F(abab) = 3 (测试是为了附加c而失败)，并且知道F(F(abab)) = F(3) = 1，这是ab的位置。

同样的事情会反复发生，直到像你说的那样，我们找到一个匹配的，或者根本没有匹配。当匹配失败时，F[]的“跳转”正在实现这个过程:测试下一个潜在的最长前缀(后缀)，如果失败，查找下一个.