Knuth-Morris-Pratt 失败表

Question

我正在为我参加的考试而学习，我正在查看 Knuth-Morris-Pratt 算法。考试的内容是失败表和 DFA 构造。我了解 DFA 构造，但我不太了解如何制作失败表。

如果我有一个模式“abababc”的例子，我如何从中构建一个失败表？解决办法是：

失败表：

0 1 2 3 4 5 6 7

0 0 0 1 2 3 4 0

但我怎么得到呢？没有代码只是对如何获得它的解释是必要的。

Answer 1

i字符串的失败表中单元格的值s定义如下：取s以位置 结尾的子串，单元格中的值是该子串i的最长适当（不是整个字符串）后缀的长度，等于到其相同长度的前缀。

让我们以您的示例为例，考虑 的值6。s长度为 6的子串是ababab。它有6个后缀：babab，abab，bab，ab和b在另一方面其应有的前缀 ababa，abab，aba，ab和a。现在很容易看出，与相同长度的前缀相等的后缀是abab和ab。其中较长的是abab，因此单元格 6 中的值是其长度 - 4。