Алгоритм Рабина-Карпа: поиск подстроки за O(n+m)

Алгоритм Рабина-Карпа (Rabin-Karp, 1987) ищет вхождения образца $P$ длины $m$ в тексте $T$ длины $n$ через хеширование подстрок. Вместо посимвольного сравнения каждой позиции он сравнивает хеш образца с хешем текущего окна текста, а само окно «прокатывает» по тексту за константу с помощью полиномиального хеша. В среднем это даёт $O(n + m)$ при разумном выборе модуля, и хотя в худшем случае алгоритм деградирует до $O(nm)$, его настоящая сила - в естественном обобщении на поиск множества образцов и на задачи вроде детекции плагиата, где десятки хешей сравниваются за один проход.

Идея: сравнивать хеши, а не строки

Наивный поиск подстроки сдвигает образец по тексту и в каждой из $n - m + 1$ позиций сравнивает до $m$ символов - это $O(nm)$. Рабин и Карп заметили: если у двух строк разные хеши, то строки заведомо различны, и сравнивать их посимвольно не нужно. Хеш - это число, его сравнение стоит $O(1)$.

План такой: один раз посчитать хеш образца $h(P)$, затем для каждого окна $T[i..i+m-1]$ посчитать его хеш и сравнить с $h(P)$. Если хеши не совпали - окно точно не образец, идём дальше. Если совпали - это кандидат, его проверяют посимвольно (потому что хеши разных строк иногда совпадают). Вся экономия в том, что хеш окна пересчитывается не за $O(m)$, а за $O(1)$ - за счёт полиномиального хеша со скользящим окном.

Полиномиальный хеш

Строку $S = s_0 s_1 \ldots s_{m-1}$ кодируют как значение многочлена по основанию $b$ по модулю $q$:

$h(S) = \left( s_0 b^{m-1} + s_1 b^{m-2} + \ldots + s_{m-1} b^0 \right) \bmod q.$

Здесь $b$ - основание (обычно простое чуть больше размера алфавита, например $b = 31$ или $b = 257$), $q$ - большой простой модуль (например $10^9 + 7$), а $s_i$ - числовой код символа. По модулю $q$ хеш умещается в машинное слово, и арифметика остаётся константной. Образец и каждое окно текста кодируются одной и той же формулой, поэтому равные строки гарантированно дают равный хеш.

Скользящее окно за O(1)

Главный трюк - пересчитать хеш соседнего окна из предыдущего без повторного суммирования. Пусть известен хеш окна $T[i..i+m-1]$. Чтобы получить хеш окна $T[i+1..i+m]$, нужно: убрать вклад ушедшего символа $T[i]$, сдвинуть остаток (домножить на $b$) и добавить пришедший символ $T[i+m]$:

$h_{i+1} = \left( \left( h_i - T[i]\, b^{m-1} \right) b + T[i+m] \right) \bmod q.$

Величина $b^{m-1} \bmod q$ считается один раз заранее. Тогда переход к следующему окну - это вычитание, два умножения и сложение по модулю, то есть $O(1)$. Именно это превращает $n - m + 1$ пересчётов из $O(nm)$ в $O(n)$. Такой хеш называют скользящим (rolling hash), и он же лежит в основе rsync и алгоритма Карпа-Рабина для двумерного поиска.

Полный алгоритм

h_p = hash(P)                # хеш образца
h_t = hash(T[0..m-1])        # хеш первого окна
power = b^(m-1) mod q
for i in 0..n-m:
    if h_t == h_p:
        if T[i..i+m-1] == P:        # проверка кандидата
            report match at i
    if i < n-m:
        h_t = ((h_t - T[i]*power)*b + T[i+m]) mod q
        h_t = (h_t + q) mod q       # убрать возможный минус

Предвычисление хешей образца и первого окна - $O(m)$. Главный цикл - $n - m + 1$ итераций, каждая по $O(1)$ плюс проверка кандидатов. Если хеш хороший и совпадений мало, кандидатов почти нет, и суммарно выходит $O(n + m)$ в среднем. Это та же асимптотика, что у алгоритма Кнута-Морриса-Пратта, но достигается она вероятностно, а не за счёт детерминированной префикс-функции.

Ложные срабатывания и модуль

Хеш отображает строки длины $m$ в числа из диапазона $[0, q)$, поэтому разные строки иногда дают один хеш - коллизия, или ложное срабатывание (spurious hit). При совпадении хешей обязательна посимвольная проверка кандидата, иначе алгоритм будет находить несуществующие вхождения.

При случайном тексте и модуле $q$ вероятность коллизии в одной позиции - порядка $1/q$. Ожидаемое число ложных срабатываний на весь текст - около $n/q$. С модулем $q \approx 10^9$ на тексте в миллион символов это доли единицы: проверки кандидатов почти не происходят, и среднее остаётся линейным.

Для защиты от намеренных коллизий (когда противник подбирает текст под ваш хеш) применяют двойное хеширование - два независимых модуля $q_1, q_2$; вероятность одновременной коллизии падает до $\approx 1/(q_1 q_2)$. Случайный выбор $b$ и $q$ из набора простых ещё надёжнее.

Худший случай и анти-хеш тесты

Если хеш-функция выбрана неудачно или текст подобран злонамеренно, хеши совпадают в каждой позиции, посимвольная проверка запускается всюду, и алгоритм деградирует до $O(nm)$. Классический пример - текст из одного повторяющегося символа и образец из того же символа: каждое окно совпадает, и проверка кандидата стоит $O(m)$.

Поэтому фиксированный публичный модуль ($q = 10^9 + 7$, $b = 31$) уязвим: на спортивных соревнованиях существуют анти-хеш тесты, валящие именно такие константы. Лечится рандомизацией: $b$ и $q$ выбираются случайно во время выполнения, и заранее построить ломающий тест становится невозможно. Детерминированной линейной гарантии у Рабина-Карпа нет - за ней идут к KMP или Z-функции.

Поиск множества образцов

Настоящее преимущество Рабина-Карпа - когда образцов несколько, но одинаковой длины $m$. Хеши всех $k$ образцов кладут в хеш-множество, а текст прокатывают одним скользящим окном. На каждой позиции проверяют, есть ли хеш окна в множестве - это $O(1)$. Один проход находит вхождения всех образцов за $O(n + km)$ в среднем, без множителя $k$ в главном цикле.

Если же образцы разной длины, единого окна не получится, и для множественного поиска удобнее алгоритм Ахо-Корасик: он строит один автомат на боре и за линейный проход находит все вхождения паттернов любой длины. Рабин-Карп остаётся выбором, когда длины совпадают (детекция дубликатов фиксированных блоков) или когда хеши и так нужны для других целей.

Применения

• Детекция плагиата и дубликатов. Тексты режут на перекрывающиеся $k$-граммы, для каждой считают скользящий хеш, и совпадающие хеши указывают на заимствованные фрагменты. Отбор по хешам (winnowing, MOSS) построен на rolling hash Рабина-Карпа.
• rsync и дедупликация. Скользящий хеш по блокам файла позволяет найти совпадающие куски между старой и новой версией и передать по сети только различия.
• Двумерный поиск образца. Поиск прямоугольного шаблона в матрице/изображении: сначала хешируют строки, потом столбцы хешей - обобщение Карпа-Рабина на два измерения.
• Поиск повторяющихся подстрок. Бинпоиск по длине повтора + хеширование всех окон этой длины даёт $O(n \log n)$ для самой длинной повторяющейся подстроки.

Частые ошибки

• Забывают проверку кандидата при совпадении хешей. Совпадение хешей - это лишь повод сравнить строки, а не доказательство равенства. Без проверки алгоритм выдаёт ложные вхождения на каждой коллизии.
• Пересчитывают хеш окна за $O(m)$. Если на каждой позиции хеш считается заново суммированием, теряется весь смысл - выходит $O(nm)$. Хеш соседнего окна обязан получаться из предыдущего за $O(1)$ через формулу скользящего окна.
• Не приводят хеш к неотрицательному по модулю. После вычитания $T[i] \cdot b^{m-1}$ значение может стать отрицательным; в языках с «математическим» остатком нужно добавить $q$ и взять модуль ещё раз, иначе хеши перестанут совпадать.
• Берут слишком маленький модуль. При $q$ порядка тысяч коллизии происходят постоянно, проверки кандидатов запускаются всюду и среднее время уезжает к квадратичному. Модуль должен быть большим простым.
• Полагаются на фиксированные $b$ и $q$ там, где есть противник. Публичные константы ломаются анти-хеш тестами. Где важны гарантии - рандомизировать параметры или брать детерминированный KMP.

FAQ

Чем алгоритм Рабина-Карпа отличается от KMP? KMP детерминированно гарантирует $O(n + m)$ за счёт префикс-функции и никогда не деградирует. Рабин-Карп даёт $O(n + m)$ только в среднем (в худшем случае $O(nm)$), зато проще обобщается на множество образцов одной длины и на хеш-задачи вроде детекции плагиата. Для одного образца с жёсткими гарантиями берут KMP; где нужны хеши или много одинаковых по длине паттернов - Рабин-Карп.

Зачем нужен модуль $q$, если можно хешировать без него? Без модуля значение полинома $s_0 b^{m-1} + \ldots$ растёт экспоненциально по $m$ и быстро выходит за машинное слово - арифметика перестаёт быть константной. Модуль $q$ удерживает хеш в пределах слова, сохраняя $O(1)$ на операцию; цена - редкие коллизии, которые отлавливает посимвольная проверка.

Можно ли искать сразу несколько образцов? Да, если все образцы одной длины $m$: их хеши кладут в хеш-множество и за один проход скользящим окном проверяют принадлежность хеша окна множеству - $O(n + km)$ в среднем. Для образцов разной длины единое окно не работает, и удобнее Ахо-Корасик с бором и суффиксными ссылками.

Коротко

Алгоритм Рабина-Карпа ищет образец $P$ длины $m$ в тексте $T$ длины $n$, сравнивая полиномиальные хеши вместо самих строк. Хеш окна $T[i..i+m-1]$ пересчитывается из соседнего за $O(1)$ скользящим окном $h_{i+1} = ((h_i - T[i] b^{m-1}) b + T[i+m]) \bmod q$, поэтому в среднем алгоритм работает за $O(n + m)$. Совпадение хешей - лишь кандидат: его обязательно проверяют посимвольно, иначе коллизии дают ложные вхождения. В худшем случае или на анти-хеш тестах алгоритм деградирует до $O(nm)$, что лечится рандомизацией $b$ и $q$ либо двойным хешированием. Главная ниша - поиск множества образцов одинаковой длины, детекция плагиата, rsync и двумерный поиск, где скользящий хеш сравнивает десятки фрагментов за один проход.