我正在为我的考试而学习，我正在复习Knuth-Morris-Pratt算法考试的重点是不及格表和DFA结构。我了解DFA构造，但我不太了解如何生成失败表。
如果我有一个模式“abababac”的例子，如何从中构建一个失败表解决办法是：
故障表：
0 1 2 3 4 5 6 7
0 0 0 1 2 3 4 0
但我该怎么做呢没有代码，只需要解释一下如何得到它是必要的。
最佳答案
字符串i的fail表中cells的值定义如下：取s的子字符串，该子字符串以i结束，单元格中的值是该子字符串的最长真值（而不是整个字符串）sufix的长度，该值等于其相同长度的前缀。
让我们以您的例子来考虑6的值。长度为6的s的子串为ababab。它有6个后缀：babab，abab，bab，ab和b另一方面，它的适当前缀是ababa，abab，aba，ab和a现在很容易看出，等于相同长度前缀的sufixes是abab和ab其中较长的是abab，因此单元格6中的值是它的长度-4。
关于algorithm - Knuth-Morris-Pratt失败表，我们在Stack Overflow上找到一个类似的问题：https://stackoverflow.com/questions/23260938/