Где применяется
1. Задача
KMP (шаг 127) при несовпадении прыгает по таблице, которую заранее построил по образцу. Рабин-Карп устроен по-другому. Он превращает каждое окно текста (кусок длиной в образец) в одно число и сравнивает числа вместо символов. Сравнить два числа можно за одну операцию, поэтому большинство позиций отсеивается сразу. Посимвольная проверка нужна, только когда числа совпали. Этот приём переносится на поиск сразу многих образцов одной длины и на поиск маленькой картинки внутри большой. Именно там он особенно выгоден.
Этот шаг из платной части
Бесплатные шаги в начале курса (их 33) открыты всем: урок, задача и тесты. Этот шаг открывается с полным доступом. Начни с бесплатного аккаунта и бесплатных шагов.
Завести бесплатный аккаунтПосмотреть, что входитНа LeetCode
Задачи, где сравнивают много подстрок одной длины, например ищут повторы или самый длинный повторяющийся кусок. Скользящий хеш обновляет каждое окно за O(1), а настоящее сравнение нужно только при равенстве хешей.
Все окна длиной 10, так что прокати хеш по строке и собери окна, чей хеш уже встречался.
Бинарный поиск по длине, и для каждой длины прокати хеш, чтобы найти окно, которое встречается дважды. Совпадение хешей проверь по тексту или возьми два модуля.
Тот же бинарный поиск по длине со скользящим хешем по числам вместо букв. При n до 1000 проходит и таблица, похожая на урок 116.
n не больше 2000, так что для каждой подстроки чётной длины сравни две её половины префиксными хешами за O(1) и складывай разные в Set.