我在 Book Algorithms 4th中学习 KMP 算法。我可以理解大部分算法，但已经在 dfa 构建过程中停留了几天。
以图案ABABAC为例。当C（dfa 的状态为 5）不匹配时，我们应该在文本中右移一个字符。所以我们所知道的模式字符是BABA。但是，在构建过程中如何计算dfa的下一个状态呢？我没看懂下面的文字：
例如，当我们在 j=5 处出现不匹配时，为了决定 DFA 应该做什么
ABABAC，我们使用 DFA 来了解完整备份会使我们处于状态 3 forBABA，因此我们可以复制dfa[][3]到dfa[][5]。
“完整备份会使我们处于状态 3 for”是什么意思，在BABA没有指定输入的情况下如何得出这个结论？而且我无法理解文本中留下的图表。谁能解释一下这是什么意思？我试图自己理解它几天，但仍然无法理解。谢谢！
匹配输入字符串时，匹配模式前5个字符后才能进入状态5，模式前5个字符为ABABA. 所以无论你使用哪个输入字符串，你都知道状态5之前的文本是“ABABA”。
因此，如果您在状态 5 中出现不匹配，您可以备份 4 个字符并再次尝试匹配。但是由于您知道在状态 5 之前必须出现什么文本，因此您实际上并不需要输入文本来确定会发生什么。当你回到同一个地方时，你可以事先弄清楚你最终会处于什么状态。
备份 4 个字符并进入状态 0：
0 : 巴巴
A 不匹配，所以前进并进入状态 0
0：ABA
A 匹配，所以转到状态 1
1：文学士
B 匹配，转到状态 2
2：一个
A 匹配，进入状态 3
3：
现在我们回到了之前看到状态 5 的输入位置，但现在我们处于状态 3。
当我们在状态 5 中得到不匹配时，这总是会发生，所以我们没有实际这样做，而是在注释中写着“当我们在状态 5 中得到不匹配时，转到状态 3”。
请注意，大多数 KMP 实现实际上会生成一个故障表，其中failure_table[5]=3. 您的示例实现正在构建完整的DFA[char][state]，因此它将所有转换从状态 3 复制到状态 5 以用于失败情况。这就是说“当我们在状态 5 中遇到不匹配时，做任何状态 3 做的事情”，结果是一样的。
在继续之前了解以上所有内容
现在让我们加快这些故障状态的计算...
当我们在状态 5 中得到不匹配时，我们可以使用我们目前拥有的 DFA 来确定如果我们从下一个可能的匹配开始备份并重新扫描输入会发生什么，方法是将 DFA 应用于“BABA”。我们最终处于状态 3，因此我们将状态 3 称为状态 5 的“失败状态”。
看起来我们必须处理 4 个模式字符来计算状态 5 的故障状态，但是当我们计算状态 4 的故障状态时，我们已经完成了大部分工作——我们将 DFA 应用于“BAB”并最终状态 2。
因此，要找出状态 5 的故障状态，我们只需从状态 4（状态 2）的故障状态开始，并处理模式中的下一个字符——输入中状态 4 之后的“A”。