如何理解KMP算法中DFA的构造过程

Question

我正在学习图书算法4中的KMP算法。我可以理解大部分的算法，但在dfa的建设过程中被困了几天。

以模式ABABAC为例。当在C(状态为5)出现不匹配时，我们应该右移文本中的一个字符。所以我们所知道的模式字符是BABA。然而，如何在建设过程中确定dfa的下一个状态？我没有理解下面的文字：

例如，要决定在j=5不匹配时DFA应该做什么，对于ABABAC，我们使用DFA来了解完全备份将使我们处于BABA的状态3，这样我们就可以将dfa[][3]复制到dfa[][5]。

“完全备份将使我们处于BABA的状态3”是什么意思，以及如何在没有指定输入的情况下得到这个结论？我无法理解剩下的图表。有人能解释一下这意味着什么吗？几天来，我一直试图自己去理解它，但仍然无法理解。谢谢!

你可以在这里读到算法4的片段。

​

​

Answer 1

当您匹配输入字符串时，只能在匹配模式的前5个字符之后才能进入状态5，模式的前5个字符是ABABA。因此，无论您使用哪个输入字符串，您都知道状态5前面的文本是"ABABA“。

因此，如果在状态5中出现不匹配，则可以备份4个字符，然后再尝试匹配。但是，由于您知道状态5之前必须显示什么文本，所以实际上不需要输入文本来确定会发生什么。你可以事先弄清楚，当你回到同一个地方时，你会处于什么样的状态。

备份4个字符并转到状态0：

0:巴巴

A不匹配，所以前进并进入状态0

0: ABA

A匹配，所以进入状态1

1: BA

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“。