Алгоритм Кнута-Морриса-Пратта (алгоритм КМП) - это один из классических алгоритмов поиска образа в строке или, проще говоря, поиска слова или фразы в тексте

МЕНЮ


Главная страница
Поиск
Регистрация на сайте
Помощь проекту
Архив новостей

ТЕМЫ


Новости ИИРазработка ИИВнедрение ИИРабота разума и сознаниеМодель мозгаРобототехника, БПЛАТрансгуманизмОбработка текстаТеория эволюцииДополненная реальностьЖелезоКиберугрозыНаучный мирИТ индустрияРазработка ПОТеория информацииМатематикаЦифровая экономика

Авторизация



RSS


RSS новости


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

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


Источник: vk.com

Комментарии: