Почему мы не сдвигаемся в этом направлении?

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 объясняется в книге "Введение в алгоритмы". Это очень похоже на метод бесконечного автомата, который может помочь вам понять его.