Алгоритм Кнута – Морриса – Пратта на основе DFA`?

Question

Алгоритм Кнута – Морриса – Пратта на основе DFA`?

Я хочу узнать, как работает алгоритм Кнута-Морриса-Пратта. Я смотрел этот учебник из Принстонского университета https://www.youtube.com/watch?v=iZ93Unvxwtw. В этом видео они используют таблицу с длиной алфавита = количество строк и длиной шаблона = количество столбцов. См. Таблицу как DFA, которая используется для обнаружения шаблона в тексте. Я думаю, что этот подход интересен, но Википедия говорит, что алгоритм Кнута-Морриса-Пратта использует таблицу префиксов с одной строкой для длины префиксов. Оба работают, и оба - это O(n+m) в термах скорости (n - длина текста, а m - длина шаблона). Но версия DFA требует больше места. Но вопрос в том, какой реальный алгоритм Кнута-Морриса-Пратта, а какой является дифференцированием?

5

algorithm dfa knuth

Источник

user1601251 04 окт '14 в 17:45

1 ответ

Решение

Другие вопросы по тегам algorithm dfa knuth

user2040251 04 окт '14 в 18:50 2014-10-04 18:50 · Accepted Answer · 2014-10-04 18:50

Реальный (согласно большинству определений, которое я видел) - это тот, что из Википедии. Идея реализовать его как DFA, вероятно, исходит из того факта, что алгоритмы Кнута-Морриса-Пратта являются частным случаем автомата Ахо-Корасика (он может работать с деревом, а не с одной строкой), который обычно реализуется таким образом (потому что таблицы префиксов для этого недостаточно).