Какова теоретическая основа алгоритма сопоставления шаблонов KMP?
Я понимаю сам алгоритм, но не понимаю, как Кнут, Моррис и Пратт изобрели этот алгоритм.
Было ли какое-либо математическое доказательство?
Можете ли вы дать ссылку, пожалуйста?
Какова теория алгоритма соответствия шаблону KMP?
Ответ 1
Алгоритм сопоставления KMP основан на конечных автоматах и работает, неявно строя таблицу перехода для автомата, который соответствует строке. Используя очень умную предварительную обработку строки в строке для поиска, можно построить соответствующий автомат, и затем автомат можно смоделировать на строке для поиска в линейном времени. Конечным результатом является алгоритм линейного времени для сопоставления строк.
Созданный автомат работает, имея одно состояние для каждого количества строки, которая была сопоставлена до сих пор. По умолчанию переходы таковы, что сопоставление следующего символа переходит к следующему состоянию на машине и считывает неверные символы, переходящие в начало. Однако некоторые фрагменты строки для поиска могут совместно использовать некоторую перекрывающуюся структуру, поэтому добавляются некоторые новые переходы, которые возвращают автомат в более раннее (но не первое) состояние при чтении символа.
Этот алгоритм обобщается алгоритмом Ахо-Корасика, который строит более сложный автомат для одновременного поиска нескольких строк.
У меня реализация этого алгоритма на моем личном сайте, который содержит подробное обсуждение фактических данных как работает алгоритм, включая доказательство правильности, более формальную интуицию за алгоритмом и объяснение того, как вывести алгоритм из первых принципов. Мне потребовалось некоторое время, чтобы собрать, но я надеюсь, что это может быть хороший ресурс, чтобы узнать больше об алгоритме.
Надеюсь, это поможет!