algorithm - Knuth-Morris-Pratt 失败表

Question

我正在准备考试，并且正在研究 Knuth-Morris-Pratt 算法。考试内容是 Fail 表和 DFA 构造。我了解 DFA 构造，但我并不真正了解如何制作失败表。

如果我有一个模式“abababc”的例子，我该如何构建一个失败表？解决方案是：

失败表：

0 1 2 3 4 5 6 7

0 0 0 1 2 3 4 0

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

Answer 1

istring 的失败表中 cell 的值s定义如下：取s结束于 position的子串， icell 中的值是该子串的最长的正确（不是整个字符串）后缀的长度等于到其相同长度的前缀。

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

Answer 2

模式 P = {abababc} P[0] = 'a'。P[1] = 'b'。P[2] = 'a'。P[3] = 'b'。P[4] = 'a'。P[5] = 'b'。P[6] = 'c'。

失败表的目的是确定最大可能的偏移（这样我们就不会错过任何模式匹配，但也不会进行不必要的比较），如果模式字符串的第一个“i”字符匹配并且中断在第 i+1 个字符处找到。

失败表中的数字表示如果模式的第一个 i 字符与文本匹配，则移位后仍有多少字符继续匹配。

令 FailTable 为 FT[]。

FT[1] - 'a' 与文本匹配。在 'b' (P[1]) 处发现中断。我们是否有一个正确的“a”后缀与“a”的正确前缀匹配？答案是否定的。因此，移位后仍继续匹配的字符串的长度为 0。因此 FT[1] = 0。

FT[2] - 'ab' 与文本匹配。在 'a' (P[2]) 处发现中断。我们是否有一个正确的“ab”后缀与“ab”的正确前缀匹配？答案是否定的。因此，移位后仍继续匹配的字符串的长度为 0。因此 FT[2] = 0。

FT[3] - 'aba' 与文本匹配。在 'b' (P[3]) 处发现中断。我们是否有一个正确的后缀 aba 与正确的前缀 aba 相匹配？答案是肯定的（'a'）。因此，移位后仍继续匹配的字符串的长度为 1。因此 FT[3] = 1。

FT[4] - 'abab' 与文本匹配。在 'a' (P[4]) 处发现中断。我们是否有一个正确的“abab”后缀与“abab”的正确前缀匹配？答案是肯定的（'ab'）。因此，移位后仍继续匹配的字符串的长度为 2。因此 FT[4] = 2。

FT[5] - 'ababa' 与文本匹配。在 'b' (P[5]) 处发现中断。我们是否有一个正确的“ababa”后缀与“ababa”的正确前缀相匹配？答案是肯定的（'aba'）。因此，移位后仍继续匹配的字符串的长度为 3。因此 FT[5] = 3。

FT[6] - 'ababab' 与文本匹配。在 'a' (P[6]) 处发现中断。我们是否有一个正确的“ababab”后缀与“ababab”的正确前缀匹配？答案是肯定的（'abab'）。因此，移位后仍继续匹配的字符串的长度为 4。因此 FT[6] = 4。

FT[7] - 'abababc' 与文本匹配。完全没有发现中断，Pattern 与文本匹配。我们是否有一个正确的“abababc”后缀与“abababc”的正确前缀相匹配？答案是否定的。因此，移位后仍继续匹配的字符串的长度为 0。因此 FT[7] = 0。

因此最终的数组是 FT = [0,0,1,2,3,4,0]

希望能帮助到你！