如何理解KMP算法中DFA构建的过程
How to understand the process of DFA construction in KMP algorithms
我正在学习算法4中的KMP算法。大部分算法我都能看懂，但一直卡在dfa构建过程中几天
以模式ABABAC为例。当C（dfa状态为5）不匹配时，我们应该在文本中右移一个字符。所以我们已知的模式字符是BABA。但是，如何在构造过程中弄清楚dfa的下一个状态呢？我没看懂下面的文字：
For example, to decide what the DFA should do when we have a mismatch at j=5, for ABABAC, we use the DFA to learn that a full backup would leave us in state 3 for BABA, so we can copy dfa[][3] to dfa[][5].
"a full backup would leave us in state 3 for BABA"是什么意思，在没有指定输入的情况下如何得出这个结论？我无法理解留给文本的图表。谁能解释一下这是什么意思？我已经尝试自己理解了几天，但仍然无法理解。谢谢！
And you can read the segment of Algorithms 4th here.
匹配输入字符串时，只有匹配到模式的前5个字符才能进入状态5，模式的前5个字符为ABABA。因此，无论您使用哪个输入字符串，您 都知道 状态 5 之前的文本是 "ABABA".
因此，如果您在状态 5 中出现不匹配，您可以可以备份 4 个字符并再次尝试匹配。但是因为您知道在状态 5 之前必须出现什么文本，所以您实际上不需要输入文本来弄清楚会发生什么。你可以事先弄清楚当你回到同一个地方时你最终会处于什么状态。
备份 4 个字符并转到状态 0:
0 : 爸爸
A不匹配，所以前进到状态0
0：阿坝州
A匹配，所以转到状态1
1: 文学学士
B匹配，进入状态2
2: A
A匹配，进入状态3
3:
现在我们回到输入中我们之前看到状态 5 的地方，但现在我们处于状态 3。
当我们在状态 5 中出现不匹配时，这总是会发生，所以我们没有实际这样做，而是做了一个注释，上面写着 "when we get a mismatch in state 5, go to state 3"。
请注意，大多数 KMP 实施实际上会失败 table，其中 failure_table[5]=3。您的示例实现正在构建完整的 DFA[char][state]，因此它会为失败案例复制从状态 3 到状态 5 的所有转换。也就是说 "when we get a mismatch in state 5, do whatever state 3 does"，结果是一样的。
在继续之前了解以上所有内容
现在让我们加快计算那些失败状态...
当我们在状态 5 中出现不匹配时，我们可以使用目前已有的 DFA 来计算如果我们备份并从下一个可能的匹配开始重新扫描输入会发生什么，方法是将 DFA 应用于 "BABA"。我们最终进入状态 3，所以让我们将状态 3 称为状态 5 的 "failure state"。
看起来我们必须处理 4 个模式字符才能计算状态 5 的失败状态，但是我们 在计算状态的失败状态时已经完成了大部分工作 4 -- 我们将 DFA 应用于 "BAB" 并以状态 2 结束。
因此，为了找出状态 5 的失败状态，我们只需从状态 4（状态 2）的失败状态开始，然后处理模式中的下一个字符——紧随其后的 "A"输入中的状态 4。
我正在学习算法4中的KMP算法。大部分算法我都能看懂，但一直卡在dfa构建过程中几天
以模式ABABAC为例。当C（dfa状态为5）不匹配时，我们应该在文本中右移一个字符。所以我们已知的模式字符是BABA。但是，如何在构造过程中弄清楚dfa的下一个状态呢？我没看懂下面的文字：
For example, to decide what the DFA should do when we have a mismatch at j=5, for
ABABAC, we use the DFA to learn that a full backup would leave us in state 3 forBABA, so we can copydfa[][3]todfa[][5].
"a full backup would leave us in state 3 for BABA"是什么意思，在没有指定输入的情况下如何得出这个结论？我无法理解留给文本的图表。谁能解释一下这是什么意思？我已经尝试自己理解了几天，但仍然无法理解。谢谢！
And you can read the segment of Algorithms 4th here.
匹配输入字符串时，只有匹配到模式的前5个字符才能进入状态5，模式的前5个字符为ABABA。因此，无论您使用哪个输入字符串，您 都知道 状态 5 之前的文本是 "ABABA".
因此，如果您在状态 5 中出现不匹配，您可以可以备份 4 个字符并再次尝试匹配。但是因为您知道在状态 5 之前必须出现什么文本，所以您实际上不需要输入文本来弄清楚会发生什么。你可以事先弄清楚当你回到同一个地方时你最终会处于什么状态。
备份 4 个字符并转到状态 0:
0 : 爸爸
A不匹配，所以前进到状态0
0：阿坝州
A匹配，所以转到状态1
1: 文学学士
B匹配，进入状态2
2: A
A匹配，进入状态3
3:
现在我们回到输入中我们之前看到状态 5 的地方，但现在我们处于状态 3。
当我们在状态 5 中出现不匹配时，这总是会发生，所以我们没有实际这样做，而是做了一个注释，上面写着 "when we get a mismatch in state 5, go to state 3"。
请注意，大多数 KMP 实施实际上会失败 table，其中 failure_table[5]=3。您的示例实现正在构建完整的 DFA[char][state]，因此它会为失败案例复制从状态 3 到状态 5 的所有转换。也就是说 "when we get a mismatch in state 5, do whatever state 3 does"，结果是一样的。
在继续之前了解以上所有内容
现在让我们加快计算那些失败状态...
当我们在状态 5 中出现不匹配时，我们可以使用目前已有的 DFA 来计算如果我们备份并从下一个可能的匹配开始重新扫描输入会发生什么，方法是将 DFA 应用于 "BABA"。我们最终进入状态 3，所以让我们将状态 3 称为状态 5 的 "failure state"。
看起来我们必须处理 4 个模式字符才能计算状态 5 的失败状态，但是我们 在计算状态的失败状态时已经完成了大部分工作 4 -- 我们将 DFA 应用于 "BAB" 并以状态 2 结束。
因此，为了找出状态 5 的失败状态，我们只需从状态 4（状态 2）的失败状态开始，然后处理模式中的下一个字符——紧随其后的 "A"输入中的状态 4。