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

字符串s的失败表中的单元格i的值定义如下:取在位置i结束的s的子串，单元格中的值是该子串的最长的本征(不是整个字符串)后缀的长度，该后缀等于其相同长度的前缀。

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

Answer 2

模式P= {abababc} P= 'a‘。P1 = 'b‘。P2 = 'a‘。P3 = 'b‘。P4 = 'a‘。P5 = 'b‘。P6 = 'c‘。

失败表的目的是识别最大可能的移位(这样我们就不会错过任何模式匹配，但也不会进行不必要的比较)，如果模式字符串的第一个"i“字符匹配，并且在第i+1个字符处发现中断。

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

让FailTable为FT[]。

FT1 - 'a‘与文本匹配。在‘b’处发现中断(P1)。我们是否有一个合适的后缀'a‘来匹配合适的前缀'a'？Ans不是。所以在移位后仍然继续匹配的字符串的长度是0。因此FT1 = 0。

FT2 - 'ab‘与文本匹配。在'a‘处发现中断(P2)。我们是否有一个正确的后缀'ab‘来匹配正确的前缀'ab'？Ans不是。所以在移位后仍然继续匹配的字符串的长度是0。因此FT2 = 0。

FT3 - 'aba‘与文本匹配。在'b‘处发现中断(P3)。我们是否有一个正确的后缀'aba‘来匹配正确的前缀'aba'？Ans是YES ('a')。所以在移位后仍然继续匹配的字符串的长度是1，因此FT3 = 1。

FT4 - 'abab‘与文本匹配。在'a‘处发现中断(P4)。我们是否有合适的后缀'abab‘来匹配合适的前缀'abab'？Ans是YES('ab')。所以在移位后仍然继续匹配的字符串的长度是2，因此FT4 = 2。

FT5 - 'ababa‘与文本匹配。在'b‘处发现中断(P5)。我们有合适的后缀'ababa‘来匹配合适的前缀'ababa’吗？Ans是YES('aba')。所以在移位后仍然继续匹配的字符串的长度是3，因此FT5 = 3。

FT6 - 'ababab‘与文本匹配。在'a‘处发现中断(P6)。我们是否有合适的后缀'ababab‘来匹配合适的前缀'ababab'？Ans是YES('abab')。所以在移位后仍然继续匹配的字符串的长度是4，因此FT6 = 4。

FT7 - 'abababc‘匹配文本。根本找不到分隔符，模式与文本匹配。我们有一个正确的后缀'abababc‘匹配正确的前缀'abababc'？Ans不是。所以在移位后仍然继续匹配的字符串的长度是0。因此FT7 = 0。

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

希望它能帮上忙！