Алгоритм Кнута-Морриса-Пратта

Алгоритм Кнута-Морриса-Пратта (алгоритм КМП) - это один из классических алгоритмов поиска образа в строке или, проще говоря, поиска слова или фразы в тексте. Эффективность алгоритма проявляется при частичном совпадении символов образа и строки. В этом случае, при несовпадении символов в дальнейшем сдвиг образа вдоль строки происходит не на один символ, как при прямом поиске, а дальше. 1. Прямой поиск vs КМП 0:28 2. Создатели алгоритма КМП 1:50 3. Первый этап алгоритма КМП 2:34 3а. Префикс и суффикс 3:01 3б. Формирование массива сдвига 7:10 3в. Программная реализация 9:45 3г. Псевдокод 14:59 4. Второй этап алгоритма КМП 15:50 4а. Поиск образа в строке 15:58 4б. Программная реализация 19:29 4в. Псевдокод 23:44 5. Сложность алгоритма КМП 25:18