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

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

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

Выберем полиномиальный хеш - [math]hash(s[1..n]) = (p^{n - 1} s[1] + ... + p^{0} s[n])[/math] mod [math]r[/math], где [math]p[/math] - это некоторое простое число, а [math]r[/math] - некоторое большое число, чтобы было меньше коллизий (обычно берётся [math]2^{32}[/math] или [math]2^{64}[/math], чтобы модуль брался автоматически - при переполнении типов;). Заметим, что если 2 строчки имеют одинаковый хэш, то они в большинстве таких случаев равны.

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

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

[math]hash(s[i + 1..i + m]) = p \cdot hash(s[i + 1..i + m - 1]) + s[i + m][/math].

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

Алгоритм

У нас есть шаблон - [math]p[1..m][/math]. У нас есть строка - [math]s[1..n][/math]. Мы хотим найти все вхождения шаблона в строку.

Давайте посчитаем [math]hash(s[1..m])[/math] и [math]hash(p[1..m])[/math].

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

Следует предподсчитать [math]p^{m}[/math].

Псевдокод

 RabinKarp (string [math]s[1..n][/math], string [math]p[1..m][/math])
      [math]hp \leftarrow hash(p[1..m])[/math]
      [math]h \leftarrow hash(s[1..m])[/math]
      for [math]i \leftarrow 1[/math] to [math]n - m + 1[/math]
           if [math]h = hp[/math]
                [math]answer.add(i)[/math]
           [math]h \leftarrow p \cdot h - p^{m} \cdot hash(s[i]) + hash(s[i + m])[/math]
      if [math]ans.size = 0[/math]
           return [math]not[/math] [math]found[/math]
      else
           return [math]answer[/math]

Новый хеш [math]h[/math] был получен с помощью быстрого пересчёта. Мы считаем, что [math]s[n + 1][/math] - пустой символ.

Время работы

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

Литература

Кормен Т., Лейзерсон Ч., Ривест Р. Алгоритмы: построение и анализ. — 2-е изд. — М.: Издательский дом «Вильямс», 2007. — С. 1296.