Knuth-Morris-Prat的轉換表

Question

我正在通過KMP算法，並且在這張幻燈片中，我下載了一個powerpoint，它顯示了一個由失敗數組構成的轉換表。我無法做出正面或反面。這個轉換表究竟與DFM相關？轉換表位於右上角。

Answer 1

過渡表描述在狀態機的所有的轉換：左手列給出了源狀態的ID，中間一列給出了導致從源狀態到過渡值目標狀態，右側列給出目標狀態的ID。相反，圖表和左手錶格僅顯示轉換的一個子集。

雖然我認爲至少有一個錯誤的條目;當遇到'a'時，左手錶或右手錶錯誤地指示了狀態1應該映射到什麼。無法確切地告訴你，但沒有看到其他幻燈片。