KMP模式查找算法
KMP pattern find algorithm
我理解了 KMP 算法，即存储值用于匹配后缀和前缀然后在字符串中搜索时不返回的概念，对于模式 "abcdabca" 前缀数组将是 {0, 0,0,0,1,2,3,1}
我明白直到 {0,0,0,0,1,2,3,_} 然后 'd' 在第 4 位最后与 'a' 不匹配。然后算法说如果 j!=0 返回到 arr[j-1]，我可以看到这给了我们正确的结果，但我不明白为什么我们要返回到之前的元素 [data]理解基础
我们返回直到找到匹配元素或 j==0，我想不出办法理解我们为什么要返回。
谢谢
在我自己的理解中，我们使用失败函数F[i]来表示最长前缀的从0开始的索引，该索引与子字符串的后缀相同S[0...i]（对于最长的，我的意思是除了整个子字符串本身之外最长的）
根据您的 OP，我认为您的实现或教程使用的是基于 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[]的"jumping" when matches fail就是实现这个过程：测试下一个可能的最长前缀（后缀），如果失败，再找下一个...
我理解了 KMP 算法，即存储值用于匹配后缀和前缀然后在字符串中搜索时不返回的概念，对于模式 "abcdabca" 前缀数组将是 {0, 0,0,0,1,2,3,1} 我明白直到 {0,0,0,0,1,2,3,_} 然后 'd' 在第 4 位最后与 'a' 不匹配。然后算法说如果 j!=0 返回到 arr[j-1]，我可以看到这给了我们正确的结果，但我不明白为什么我们要返回到之前的元素 [data]理解基础
我们返回直到找到匹配元素或 j==0，我想不出办法理解我们为什么要返回。
谢谢
在我自己的理解中，我们使用失败函数F[i]来表示最长前缀的从0开始的索引，该索引与子字符串的后缀相同S[0...i]（对于最长的，我的意思是除了整个子字符串本身之外最长的）
根据您的 OP，我认为您的实现或教程使用的是基于 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[]的"jumping" when matches fail就是实现这个过程：测试下一个可能的最长前缀（后缀），如果失败，再找下一个...