我正在准备考试，正在研究 Knuth-Morris-Pratt 算法。考试内容是不及格表和 DFA 构建。我了解 DFA 构造，但我不太了解如何制作失败表。
如果我有一个模式“abababc”的示例，如何从中构建失败表？解决办法是：
失败表：
0 1 2 3 4 5 6 7
0 0 0 1 2 3 4 0
但我怎样才能得到它呢？不需要代码，只需解释如何获取它是必要的。
细胞的价值i在字符串的失败表中s定义如下：取子串s结束于位置i，单元格中的值是该子字符串的最长固有（不是整个字符串）后缀的长度，并且等于其相同长度的前缀。
让我们以您的示例为例并考虑以下值6。的子串s长度为 6 的是ababab。它有 6 个后缀：babab, abab, bab, ab and b另一方面，它的正确前缀是ababa, abab, aba, ab and a。现在很容易看出，与相同长度的前缀相等的后缀是abab and ab。其中较长的是abab因此单元格 6 中的值是它的长度 -4.
本文内容由网友自发贡献，版权归原作者所有，本站不承担相应法律责任。如您发现有涉嫌抄袭侵权的内容，请联系:hwhale#tublm.com(使用前将#替换为@)
