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

2012-03-24T18:45:12Z

178.178.1.62: /* Алгоритм */

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

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

Выберем полиномиальный хеш - <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>.

Псевдо-код:
'''1:''' function RabinKarp(string s[1..n], string p[1..m])
'''2:''' hp := hash(p[1..m])
'''3:''' h := hash(s[1..m])
'''4:''' for i from 1 to (n - m + 1)
'''5:''' if h = hp
'''6:''' answer.add(i)
'''7:''' h := p <tex>\cdot</tex> h - <tex>p^{m}</tex>s[i] + s[i + m]
'''8:''' if ans.size = 0
'''9:''' return not found
'''10:''' else
'''11:''' return answer

7 строка была получена с помощью быстрого пересчёта хеша. Мы считаем, что <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-03-24T17:54:21Z

178.178.1.62:

==Постановка задачи==
Имеются строки <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>.

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

'''Naive_String_Matcher''' (<tex>T,P</tex>)
<tex>n \leftarrow length[T]</tex>
<tex>m \leftarrow length[P]</tex>
'''for''' <tex>s \leftarrow 0</tex> to <tex>n - m</tex>
'''do if''' <tex>T[s + 1 .. s + m]</tex> = <tex>P[1..m]</tex>
'''then''' 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]

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

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