Поиск подстроки в строке с использованием хеширования. Алгоритм Рабина-Карпа

Алгоритм Рабина-Карпа предназначен для поиска подстроки в строке.

Метод хеширования

Наивный алгоритм поиска подстроки в строке работает за [math]O\left(n^2\right)[/math] в худщем случае - слишком долго. Чтобы ускорить этот процесс, можно воспользоваться методом хеширования.

Определение:

Пусть дана строка [math]s[1..n][/math]. Тогда полиномиальным хешем строки [math]s[/math] называется число [math]h = \mathrm{hash}(s[1..n]) = p^{n - 1} s[1] + ... + p^{0} s[n][/math], где [math]p[/math] - некоторое натуральное число, а [math]s[i][/math] - код [math]i[/math]-ого символа строки [math]s[/math].

Проблему переполнения при вычислении хешей довольно больших строк можно решить так: будем считать хеши по модулю [math]r[/math] - некоторому большому числу (будем брать [math]r =2^{64}[/math], чтобы модуль брался автоматически при переполнении типов). Число [math]p[/math] для их подсчета должно быть, во-первых, больше кода самого большого символа в строках, а во-вторых, взаимно простым с модулем (в нашем случае — с 2^{64}, т.е. оно должно быть нечетным).

Использование полиномиального хеша именно с убывающими степенями [math]p[/math] позволяет нам, зная хеш некоторой строки, посчитать хеш строки, образованной удалением первого символа и добавлением символа в конец, за [math]O(1)[/math]:

[math]\mathrm{hash}(s[i + 1..i + m - 1]) = (\mathrm{hash}(s[i..i + m - 1]) - p^{m - 1} s[i]) \bmod r[/math].

[math]\mathrm{hash}(s[i + 1..i + m]) = (p \cdot \mathrm{hash}(s[i + 1..i + m - 1]) + s[i + m]) \bmod r[/math].

Получается : [math]\mathrm{hash}(s[i + 1..i + m]) = (p \cdot \mathrm{hash}(s[i..i + m - 1]) - p^{m} s[i] + s[i + m]) \bmod r[/math].

Алгоритм

Алгоритм начинается с подсчета [math]\mathrm{hash}(s[1..m])[/math] и [math]\mathrm{hash}(p[1..m])[/math].

Для [math]i \in [1..n - m + 1][/math] вычисляется [math]\mathrm{hash}(s[i..i + m - 1])[/math] и сравнивается с [math]\mathrm{hash}(p[1..m])[/math]. Если они оказались равны, то образец [math]p[/math] скорее всего содержится в строке [math]s[/math] начиная с позиции [math]i[/math], хотя возможны и ложные срабатывания алгоритма. Если требуется свести такие срабатывания к минимуму или исключить вовсе, то применяют сравнение некоторых символов из этих строк, которые выбраны случайным образом, или применяют явное сравнение строк, как в наивном алгоритме поиска подстроки в строке. В первом случае проверка произойдет быстрее, но вероятность ложного срабатывания, хоть и небольшая, останется. Во втором случае проверка займет время, равное длине образца, но полностью исключит возможность ложного срабатывания.

Для ускорения работы алгоритма оптимально предпосчитать [math]p^{m}[/math].

Псевдокод

Приведем пример псевдокода, который находит все вхождения строки [math]w[/math] в строку [math]s[/math] и возвращает массив позиций, откуда начинаются вхождения.

vector<int> rabinKarp (s : string, w : string):
   vector<int> answer
   int n = s.length
   int m = w.length
   int hashS = hash(s[1..m])
   int hashW = hash(w[1..m])
   for i = 1 to n - m + 1
        if hashS == hashW
             answer.add(i)
        hashS = (p * hashS - p[math]^{m}[/math] * hash(s[i]) + hash(s[i + m])) mod r // r — некоторое большое число, p — некоторое просто число
   return answer

Новый хеш [math]hashS[/math] был получен с помощью быстрого пересчёта. Для сохранения корректности алгоритма нужно считать, что [math]s[n + 1][/math] — пустой символ.

Рекомендуется брать [math]r = 2^{64}[/math] (чтобы модуль брался автоматически при переполнении типов), а [math]p[/math] - больше кода самого большого символа в строках.

Время работы

Изначальный подсчёт хешей выполняется за [math]O(m)[/math].

Каждая итерация выполняется за [math]O(1)[/math], В цикле всего [math]n - m + 1[/math] итераций.

Итоговое время работы алгоритма [math]O(n + m)[/math].

Надёжность

Если количество подстрок данной строки превышает количество хешей (а это выполняется тогда, когда длина строки больше [math]r[/math], так как количество различных значений полиномиального хеша совпадает с [math]r[/math]), то наступление коллизий неизбежно. Но даже при относительно небольших строках вероятность коллизий может быть высока, не говоря уже о способах составления специальных строк, где алгоритм на хешах выдаёт частые ложные срабатывания.

Например, возьмем за [math]S[/math] строку Туэ-Морса длиной [math]2^{k}[/math], [math]r = 2^{64}[/math], [math]p[/math] - любое просто число.

Обозначим за [math]S_k[/math] строку [math]S[/math] для фиксированного [math]k[/math] , а за [math]not S_k[/math] строку после замены [math]A[/math] на [math]B[/math] и наоборот.

Покажем, что при [math]k = 10[/math], [math]\mathrm{hash}(S_k) = \mathrm{hash}(not S_k)[/math]. Ведь если это так, то сами по себе [math]S_k[/math] и [math]not S_k[/math] встретятся в больших строках много-много раз.

Разберемся, что значит [math]\mathrm{hash}(S_k) = \mathrm{hash}(not S_k)[/math]. Можно смело взять вместо [math]A[/math] и [math]B[/math] нули и единицы в коэффициентах многочлена - тем самым мы просто сократим обе части на [math]\sum\limits_{i=0}^{2^k - 1} 65 \cdot p^i[/math].

Что такое [math]\mathrm{hash}(S_k) - \mathrm{hash}(not S_k)[/math]? Нетрудно сообразить, что эта величина есть: [math]T = p^{0} - p^{1} - p^{2} + p^{3} - p^{4} + p^{5} + p^{6} - p^{7} ... \pm p^{2^k - 1}[/math]. То есть это знакопеременная сумма степеней [math]p[/math], где знаки чередуются по тому же правилу, что и символы в строке.

Будем последовательно выносить из этой суммы множители за скобку:

[math]T = (p^{1} - 1)( - p^{0} + p^{2} + p^{4} - p^{6} + p^{8} - p^{10} - p^{12} + p^{14} ...) = [/math]

[math] = (p^{1} - 1)(p^{2} - 1)(p^{0} - p^{4} - p^{8} + p^{12} ...) = ... = (p^{1} - 1)(p^{2} - 1)(p^{4} - 1) ... (p^{2^{k-1}} - 1).[/math]

А теперь самое главное - эта величина по модулю [math]2^{64}[/math] моментально занулится. Почему?

Давайте поймём, на какую максимальную степень двойки делится каждая из [math]k - 1[/math] скобок. Заметим, что [math](i + 1)[/math]-ая скобка [math]p^{2^{i + 1}}  -  1 = (p^{2i}  -  1)(p^{2i}  +  1)[/math] делится на [math]i[/math]-ую и ещё на какое-то чётное число [math]p^{2i}  +  1[/math]. Это означает, что если [math]i[/math]-ая скобка делится на [math]2^r[/math], то [math](i + 1)[/math]-ая скобка делится по меньшей мере на [math]2^{r + 1}[/math].

Вот и выходит, что [math](p^1 - 1)(p^2 - 1)(p^4 - 1)...(p^{2k - 1}  -  1)[/math] делится по меньшей мере на [math]2 \cdot 2^2 \cdot 2^3 \cdot ...  =  2^{k(k - 1) / 2}[/math]. Значит достаточно взять [math]k \gt = 12[/math], чтобы в рассматриваемой строке было очень много различных подстрок, чьи хеши совпадут.

См. также

• Наивный алгоритм поиска подстроки в строке
• Поиск наибольшей общей подстроки двух строк с использованием хеширования

Источники информации

• Кормен, Томас Х., Лейзерсон, Чарльз И., Ривест, Рональд Л., Штайн Клиффорд Алгоритмы: построение и анализ, 3-е издание. Пер. с англ. — М.:Издательский дом "Вильямс", 2014. — 1328 с.: ил. — ISBN 978-5-8459-1794-2 (рус.) — страницы 1036–1041.
• Codeforces: Anti-hash test