algorithm - 我们为什么不这样转变？

Question

在研究字符串的 Knuth-Morris-Pratt 算法时：

ABC ABCDAB ABCDAB

对于模式：

ABCDABD

我被困在一个步骤上。我将突出显示我目前卡住的步骤。

ABC ABCDAB ABCDAB
ABCDABD

ABC ABCDAB ABCDAB
   ABCDABD

ABC ABCDAB ABCDAB
    ABCDABD

ABC ABCDAB ABCDAB
        ABCDABD--------------------(WHY THIS ?)

我不明白上面的步骤。我希望上述步骤是：

ABC ABCDAB ABCDAB
          ABCDABD

请解释“正确”步骤的逻辑/原因。

Answer 1

当 ' ' 与 'D' 比较时，它会发现不匹配。并且这个算法“记住”之前的“AB”是比较的，所以它需要检查不匹配的字符是否是 'C' 。

KMP 方法的思想在“算法简介”一书中进行了解释。它与无限状态机方法非常相似，这可能有助于您理解它。