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

2012-04-15T15:10:12Z

178.178.11.56:

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

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

Следует использовать полиномиальный хеш {{---}} <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>O(1)</tex>:

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

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

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

==Алгоритм==

Есть шаблон {{---}} <tex>p[1..m]</tex> и строка {{---}} <tex>s[1..n]</tex>. Нужно найти все вхождения шаблона в строку.

В начале вычисляются <tex>hash(s[1..m])</tex> и <tex>hash(p[1..m])</tex>.

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

Следует предподсчитать <tex>p^{m}</tex>.

==Псевдокод==
'''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<tex>^{m}</tex> * hash(s[i]) + hash(s[i + m)
'''if''' answer.size() == 0
'''return''' not found
'''else'''
'''return''' answer

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

==Время работы==

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

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

Наивный алгоритм поиска подстроки в строке

2012-04-15T15:07:47Z

178.178.11.56: /* Псевдокод */

==Постановка задачи==
Имеются строки <tex>T[1 .. n]</tex> и <tex>P[1 .. m]</tex> такие, что <tex>n</tex> <tex>\ge</tex> <tex>m</tex> и элементы этих строк <tex>-</tex> символы из конечного алфавита <tex> \sum </tex>. Говорят, что строка <tex>P</tex> встречается в строке <tex>T</tex> со сдвигом <tex>s</tex>, если <tex> 0 \le s \le n-m</tex> и <tex>T[s + 1 .. s + m]</tex> = <tex>P[1..m]</tex>. Если строка <tex>P</tex> встречается в строке <tex>T</tex>, то <tex>P</tex> является подстрокой <tex>T</tex>. Требуется проверить, является ли строка <tex>P</tex> подстрокой <tex>T</tex>.

==Алгоритм==
В наивном алгоритме поиск всех допустимых сдвигов производится с помощью цикла, в котором проверяется условие <tex>T[s + 1 .. s + m]</tex> = <tex>P[1..m]</tex> для каждого из <tex> n-m+1</tex> возможных значений <tex>s</tex>.

==Псевдокод==

'''naiveStringMatcher''' (T, P)
n = length(T)
m = length(P)
'''for''' s = 0 '''to''' n - m
'''if''' T[s + 1 .. s + m] = P[1..m]
print()

==Время работы==
Алгоритм работает за <tex>O(m * (n - m))</tex>. В худшем случае <tex> m = n / 2 </tex>, что дает <tex> O(n^2/4) = O(n^2) </tex>.

== Литература ==
* ''Кормен Т., Лейзерсон Ч., Ривест Р.'' Алгоритмы: построение и анализ.[http://wmate.ru/ebooks/?dl=380&mirror=1] — 2-е изд. — М.: Издательский дом «Вильямс», 2007. — С. 1296.

Викиконспекты - Вклад участника [ru]

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

Наивный алгоритм поиска подстроки в строке