Какова теория алгоритма сопоставления шаблонов KMP? [закрыто]

Алгоритм сопоставления KMP основан на конечных автоматах и работает путем неявного построения таблицы переходов для автомата, который соответствует строке. Используя очень умную предварительную обработку строки в линейном времени для поиска, можно построить соответствующий автомат, а затем можно смоделировать автомат на строке для поиска в линейном времени. Итоговым результатом является алгоритм линейного времени для сопоставления строк.

Созданный автомат работает, имея одно состояние для каждого количества строки, которая до сих пор соответствовала. По умолчанию переходы таковы, что сопоставление следующего символа переходит к следующему состоянию в машине и считывание недопустимых символов переходит обратно в начало. Однако некоторые фрагменты строки для поиска могут иметь общую перекрывающуюся структуру, поэтому добавляются некоторые новые переходы, которые возвращают автомат к более раннему (но не первому) состоянию при чтении символа.

Этот алгоритм обобщен алгоритмом Aho-Corasick, который строит более сложный автомат для поиска нескольких строк одновременно.

У меня есть реализация этого алгоритма на моем личном сайте , в котором содержится подробное обсуждение фактических деталей работы алгоритма, включая доказательство правильности, более формальную интуицию, стоящую за алгоритм и объяснение того, как вывести алгоритм из первых принципов. Это заняло у меня некоторое время, но я надеюсь, что это может быть хорошим ресурсом, чтобы узнать больше об алгоритме.

Надеюсь, это поможет!