string - 了解 Knuth-Morris-Pratt 算法

Question

有人能给我解释一下吗？我一直在阅读它，但仍然很难理解。

文本:ababdbaababa
图案: ababa

ababa 的表是 -1 0 0 1 2。

我想我明白表格是如何构建的，但是，我不明白一旦发生不匹配如何移动。好像我们换类的时候连 table 都不用？

我们什么时候使用表格？

Answer 1

这里我简要描述了计算前缀函数和移动这里的文本。

更多信息:Knuth–Morris–Pratt string search algorithm

在文本中移动:

Text:     ABC ABCDAB ABCDABCDABDE
Pattern : ABCDABD

场景 1 - Pattern 和 Text 中有一些匹配的字符。
例如 1:这里有 3 个匹配的字符。

从表中获取 3 个字符的值。 (索引 2，ABC)即 0因此 shift = 3 - 0 即 3

例2:这里有6个匹配的字符。

从表中获取 6 个字符的值。 (索引 5，ABCDAB)即 2因此 shift = 6 - 2 即 4

场景 2 - 如果没有匹配的字符则移动一个。