algorithm - Knuth-Morris-Pratt 的转换表

Question

我正在研究 KMP 算法，在这张幻灯片中，我下载了一个 powerpoint，它显示了一个由算法的失败数组制成的转换表。我无法理解它的正面或反面。与 DFM 相关的转换表究竟显示了什么？转换表在右上角。

Answer 1

转换表描述了状态机中所有的转换:左边的列给出了源状态的 ID，中间的列给出了导致从源状态转换到当前状态的值目标状态，右侧列给出了目标状态的 ID。相比之下，图表和左侧表格仅显示了转换的一个子集。

不过我认为至少有一个错误条目；当遇到“a”时，左 watch 格或右 watch 格关于状态 1 应该映射到什么是错误的。在没有看到其余幻灯片的情况下，无法确定地告诉您是哪一个。