Blog. Just Blog

Поиск подстроки в строке по алгоритму Кнута-Морриса-Пратта

11.06.2024 | Категория: Образ мышления: Assembler | Автор: ManHunter

Поиск подстроки в строке по алгоритму Кнута-Морриса-Пратта

Алгоритм Кнута-Морриса-Пратта, он же классический "КМП-алгоритм" - один из самых эффективных алгоритмов поиска подстроки в строке. Оптимизация достигается за счет того, что при возникновении несоответствия само искомое слово содержит достаточно информации, чтобы определить, где может начаться следующее совпадение, минуя лишние проверки. Скорость работы алгоритма линейно зависит от объема входных данных, то есть невозможно разработать более эффективный алгоритм с точки зрения вычислительной сложности.

Читать статью целиком »
Просмотров: 328 | Комментариев: 1

Наверх
Powered by PCL's Speckled Band Engine 0.2 RC3
© ManHunter / PCL, 2008-2024
При использовании материалов ссылка на сайт обязательна
Время генерации: 0.08 сек. / MySQL: 1 (0.0164 сек.) / Память: 4.5 Mb
Наверх