Knuth-Morris-Prat过渡表

Question

我正在研究KMP算法，在这张幻灯片中，我下载了一个powerpoint，它显示了一个从该算法的fail数组中生成的转换表。我不能用它来作正面或反面判断。这个转换表相对于DFM到底显示了什么？转换表位于右上角。

​

​

Answer 1

转换表描述状态机中的所有转换:左侧列提供源状态的ID，中间列提供导致从源状态转换到目标状态的值，右边列提供目标状态的ID。相比之下，图和左手表只显示转换的子集。

但是，我认为至少有一个错误条目；左手表或右手表在遇到'a‘时应该映射到什么状态1的问题上都是错误的。在没有看到其他幻灯片的情况下，你无法确定哪一个是正确的。