algorithm - なぜこのようにシフトしないのですか？

Question

文字列のクヌース–モリス–プラット アルゴリズムを勉強している間:

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 法の考え方は、本「アルゴリズム入門」で説明されています。これは、無限ステート マシン メソッドに非常に似ているため、理解するのに役立ちます。