Подготовка к алгоритмическим задачам
Алгоритм Рабина-Карпа: поиск подстроки через хеширование
Коротко
| Параметр | Значение |
|---|---|
| Средний случай | O(n + m) |
| Худший случай | O(n · m) при плохих хешах |
| Память | O(1) |
| Сильная сторона | поиск нескольких образцов сразу |
Где n — длина текста, m — длина образца.
Идея: сравнивать числа вместо строк
Наивный поиск подстроки на каждой позиции сравнивает символы посимвольно — O(n·m).
Рабин и Карп предложили другое: посчитать хеш образца и хеш каждого окна текста той же длины. Числа сравниваются за одну операцию, а не за m.
текст: a b c d e
образец: c d
hash("cd") = 199
окна: "ab"=145 "bc"=172 "cd"=199 ← совпало!
Проблема очевидна: пересчёт хеша каждого окна с нуля стоит O(m), и мы ничего не выиграли. Здесь и появляется главный приём.
Скользящий хеш
Нужна хеш-функция, которую можно пересчитать за O(1) при сдвиге окна на один символ. Такую даёт полиномиальный хеш:
hash(s) = s[0]·p^(m-1) + s[1]·p^(m-2) + ... + s[m-1]·p^0 (mod M)
где p — простое число чуть больше размера алфавита, M — большой простой модуль.
При сдвиге окна вправо: вычитаем вклад ушедшего символа, умножаем на p, прибавляем новый символ.
new_hash = (old_hash - s[left] * p^(m-1)) * p + s[right]
Три арифметические операции вместо цикла по m символам.
Реализация на Python
def rabin_karp(text: str, pattern: str) -> list[int]: n, m = len(text), len(pattern) if m > n or m == 0: return [] p = 31 # основание: чуть больше размера алфавита mod = 10 ** 9 + 7 # большой простой модуль # p^(m-1) понадобится для вычитания старшего разряда high_power = pow(p, m - 1, mod) def char_code(c: str) -> int: return ord(c) - ord('a') + 1 # хеши образца и первого окна pattern_hash = 0 window_hash = 0 for i in range(m): pattern_hash = (pattern_hash * p + char_code(pattern[i])) % mod window_hash = (window_hash * p + char_code(text[i])) % mod result = [] for i in range(n - m + 1): # хеши совпали — проверяем посимвольно (защита от коллизии) if window_hash == pattern_hash and text[i:i + m] == pattern: result.append(i) # сдвигаем окно за O(1) if i < n - m: window_hash = (window_hash - char_code(text[i]) * high_power) % mod window_hash = (window_hash * p + char_code(text[i + m])) % mod window_hash %= mod return result print(rabin_karp('abracadabra', 'abra')) # [0, 7] print(rabin_karp('aaaaa', 'aa')) # [0, 1, 2, 3]
Почему обязательна проверка после совпадения хешей
Строка text[i:i+m] == pattern кажется лишней — хеши ведь совпали. Но хеш сжимает строку произвольной длины в одно число, поэтому коллизии неизбежны: разные строки могут дать одинаковый хеш.
Без проверки алгоритм выдавал бы ложные срабатывания. С проверкой он корректен всегда, а её стоимость O(m) платится редко — только при совпадении хешей.
Вероятность коллизии при хорошем модуле около 1/M. Для M = 10⁹+7 это примерно один шанс на миллиард — то есть проверка почти никогда не срабатывает впустую.
Выбор параметров
Основание p должно быть больше размера алфавита. Для строчных латинских букв берут 31 или 53, для смешанного алфавита — 131 или 257. Простое число предпочтительнее.
Модуль M должен быть большим простым. Популярные варианты: 10⁹ + 7, 10⁹ + 9, 2⁶¹ − 1. Чем больше модуль, тем реже коллизии.
Двойное хеширование — если нужна повышенная надёжность, считают два хеша с разными модулями и сравнивают пару. Вероятность одновременной коллизии становится порядка 1/M², то есть пренебрежимой.
Обработка отрицательных значений
В Python % всегда возвращает неотрицательный результат, поэтому строка
window_hash = (window_hash - char_code(text[i]) * high_power) % mod
работает корректно. В C++, Java или JavaScript остаток может быть отрицательным, и потребуется явная поправка:
hash = ((hash - code * highPower) % mod + mod) % mod;
Это классический источник багов при переносе алгоритма на другой язык.
Главное преимущество: несколько образцов сразу
Здесь Рабин-Карп обходит KMP. Если нужно найти в тексте не один образец, а много, достаточно посчитать хеши всех образцов и сложить их в множество.
def rabin_karp_multi(text: str, patterns: list[str]) -> dict: """Все образцы должны быть одной длины.""" if not patterns: return {} m = len(patterns[0]) p, mod = 31, 10 ** 9 + 7 def string_hash(s: str) -> int: h = 0 for c in s: h = (h * p + ord(c) - ord('a') + 1) % mod return h # хеш -> список образцов с таким хешем pattern_hashes = {} for pattern in patterns: pattern_hashes.setdefault(string_hash(pattern), []).append(pattern) high_power = pow(p, m - 1, mod) window_hash = string_hash(text[:m]) found = {} for i in range(len(text) - m + 1): if window_hash in pattern_hashes: window = text[i:i + m] if window in pattern_hashes[window_hash]: found.setdefault(window, []).append(i) if i < len(text) - m: window_hash = (window_hash - (ord(text[i]) - ord('a') + 1) * high_power) % mod window_hash = (window_hash * p + ord(text[i + m]) - ord('a') + 1) % mod return found print(rabin_karp_multi('abcdabc', ['abc', 'bcd', 'xyz'])) # {'abc': [0, 4], 'bcd': [1]}
Один проход по тексту находит все образцы. KMP пришлось бы запускать по разу на каждый.
Сравнение с KMP
| Рабин-Карп | KMP | |
|---|---|---|
| Средний случай | O(n + m) | O(n + m) гарантированно |
| Худший случай | O(n·m) | O(n + m) |
| Предподсчёт | O(m) | O(m) |
| Память | O(1) | O(m) |
| Много образцов | один проход | по проходу на каждый |
| Двумерный поиск | легко обобщается | сложно |
| Сложность кода | проще | сложнее |
Вывод: один образец — KMP (гарантированная линейность), много образцов или двумерный поиск — Рабин-Карп.
Для поиска большого количества образцов разной длины есть ещё более подходящий инструмент — алгоритм Ахо-Корасик на основе префиксного дерева.
Другие применения полиномиального хеша
Скользящий хеш полезен не только для поиска подстроки.
Сравнение подстрок за O(1). Предподсчитав префиксные хеши, можно сравнивать любые две подстроки одной длины за константное время. Это база для многих задач на строки.
Поиск повторяющихся подстрок заданной длины — сложить хеши всех окон в множество.
Наибольшая общая подстрока двух строк — бинарный поиск по длине плюс хеши.
Обнаружение плагиата — сравнение хешей фрагментов документов. Алгоритм Rabin fingerprint используется в системах дедупликации данных.
Частые ошибки
Пропущенная проверка на коллизию. Алгоритм начнёт выдавать ложные совпадения. Ошибка редкая и потому особенно неприятная.
Маленький модуль. При mod = 1000 коллизии станут постоянными, и алгоритм выродится в наивный поиск.
Отрицательный остаток. В языках, где % может вернуть минус, — гарантированный баг.
Пересчёт хеша окна с нуля. Сводит на нет весь смысл алгоритма: сложность возвращается к O(n·m).
Что запомнить
- Сравниваем хеши окон вместо посимвольного сравнения строк.
- Полиномиальный хеш пересчитывается при сдвиге окна за O(1).
- Проверка совпадения символов после совпадения хешей обязательна — коллизии существуют.
- Модуль берите большим простым, для надёжности используйте двойное хеширование.
- Главное преимущество перед KMP — поиск множества образцов за один проход.
Решай алгоритмические задачи как профи
