Поиск подстроки, сравнение и индексация текста за линейное время вместо квадратичного перебора.
Ключевые тезисы
- строит префикс-функцию и не откатывается назад по тексту — линейный поиск.
- строк (Рабина — Карпа) сравнивает подстроки за константу ценой риска коллизии.
- — динамика на двух строках, основа нечёткого поиска и исправления опечаток.
Видеолекции
Записи университетских курсов, где эта тема звучит. Тайм-кодов у них нет, поэтому открываются они с начала.
Проверить себя
Проверить себя: Алгоритмы и структуры данныхТема встречается в тесте по направлениям — ошибки приведут обратно на эту страницу.
Глава «Алгоритмы и структуры данных» последний раз правилась . Нашли ошибку — напишите.