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

Материал из Викиконспекты
Перейти к: навигация, поиск
(Метод хеширования)
Строка 2: Строка 2:
 
==Метод хеширования==
 
==Метод хеширования==
  
Для решения задачи удобно использовать полиномиальный хеш, так его легко пересчитывать, {{---}} <tex>hash(s[1..n]) = (p^{n - 1} s[1] + ... + p^{0} s[n])</tex> mod <tex>r</tex>, где <tex>p</tex> {{---}} это некоторое простое число, а <tex>r</tex> {{---}} некоторое большое число, чтобы было меньше коллизий (обычно берётся <tex>2^{32}</tex> или <tex>2^{64}</tex>, чтобы модуль брался автоматически при переполнении типов). Стоит обратить внимание, что если 2 строчки имеют одинаковый хэш, то они в большинстве таких случаев равны.
+
Для решения задачи удобно использовать полиномиальный хеш, так его легко пересчитывать: <tex>hash(s[1..n]) = (p^{n - 1} s[1] + ... + p^{0} s[n])\bmod r</tex>, где <tex>p</tex> {{---}} это некоторое простое число, а <tex>r</tex> {{---}} некоторое большое число, чтобы было меньше коллизий (обычно берётся <tex>2^{32}</tex> или <tex>2^{64}</tex>, чтобы модуль брался автоматически при переполнении типов). Стоит обратить внимание, что если 2 строчки имеют одинаковый хэш, то они в большинстве таких случаев равны.
  
 
При удалении первого символа строки и добавлении символа в конец считать хеш новой строки при помощи хеша изначальной строки возможно за <tex>O(1)</tex>:
 
При удалении первого символа строки и добавлении символа в конец считать хеш новой строки при помощи хеша изначальной строки возможно за <tex>O(1)</tex>:

Версия 18:59, 8 июня 2012

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

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

Для решения задачи удобно использовать полиномиальный хеш, так его легко пересчитывать: [math]hash(s[1..n]) = (p^{n - 1} s[1] + ... + p^{0} s[n])\bmod 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]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 (s[1..n], p[1..m])
      hp = hash(p[1..m])
      h = hash(s[1..m])
      for i = 1 to n - m + 1
           if h = hp
                answer.add(i)
           h = p * h - p[math]^{m}[/math] * hash(s[i]) + hash(s[i + m])
      if answer.size() == 0
           return not found
      else
           return answer

Новый хеш [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.

Ссылки