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

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

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

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

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

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

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

Для работы алгоритма потребуется считать хеш подстроки [math]s[i..j][/math]. Делать это можно следующим образом:

Рассмотрим хеш [math]s[0..j][/math]:

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

Разобьем это выражение на две части:

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

Вынесем из последней скобки множитель [math]p^{i}[/math]:

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

Выражение в первой скобке есть не что иное, как хеш подстроки [math]s[0..i-1][/math], а во второй — хеш нужной нам подстроки [math]s[i..j][/math]. Итак, мы получили, что:

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

Отсюда получается следующая формула для [math]\mathrm{hash}(s[i..j])[/math]:

[math]\mathrm{hash}(s[i..j]) = (1/p^{i})(\mathrm{hash}(s[0..j]) - \mathrm{hash}(s[0..i-1]))[/math]

Однако, как видно из формулы, чтобы уметь считать хеш для всех подстрок начинающихся с [math]i[/math], нужно предпосчитать все [math]p^{i}[/math] для [math]i \in [0..n - 1][/math]. Это займет много памяти. Но поскольку нам нужны только подстроки размером [math]m[/math] [math]{-}[/math] мы можем подсчитать хеш подстроки [math]s[0..m-1][/math], а затем пересчитывать хеши для всех [math]i \in [0..n - m][/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^{i} s[i] + s[i + m]) \bmod r[/math].

Решение

Алгоритм

Алгоритм начинается с подсчета [math]\mathrm{hash}(s[0..m-1])[/math] и [math]\mathrm{hash}(p[0..m-1])[/math], а также с подсчета [math]p^{m}[/math], для ускорения ответов на запрос.

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

Если требуется найти индексы вхождения нескольких образцов, или сравнить две строки [math]{-}[/math] выгоднее будет предпосчитать все степени [math]p[/math], а также хеши всех префиксов строки [math]s[/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[0..m - 1])
   int hashW = hash(w[0..m - 1])
   for i = 0 to n - m
        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]O(m)[/math].

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

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

Однако, если требуется исключить ложные срабатывания алгоритма полностью, т.е. придется проверить все полученные позиции вхождения на истинность, то в худшем случае итоговое время работы алгоритма будет [math]O(n[/math] [math]\cdot[/math] [math]m)[/math].

Сравнение с другими алгоритмами

Преимущества:

• Быстрая скорость работы — [math]O(n + m)[/math], где [math]n[/math] — длина строки, [math]m[/math] — длина образца;
• Простая и понятная реализация;

Недостатки:

• Возможно подобрать входные данные так, что количество ложных срабатываний будет недопустимо большим;

См. также

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

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

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