Изменения

Алгоритм Рабина — -Карпа — это предназначен для [[Наивный алгоритм поиска подстроки в строке#Постановка задачи| поиска подстроки в строке]].==Метод хеширования== [[Наивный алгоритм поиска подстроки в строке]] работает за <tex>O\left(n^2\right)</tex> в худшем случае — слишком долго. Чтобы ускорить этот процесс, используя хешированиеможно воспользоваться методом [[Хеш-таблица#Хеширование|хеширования]].{{Определение|definition = Пусть дана строка <tex>s[0..n-1]</tex>. Тогда '''полиномиальным хешем''' (англ. ''polynomial hash'') строки <tex>s</tex> называется число <tex>h = \mathrm{hash}(s[0..n-1]) = p^{0} s[0] + ... + p^{n - 1} s[n-1]</tex>, где <tex>p</tex> — некоторое простое число, а <tex>s[i]</tex> <tex>{-}</tex> код <tex>i</tex>-ого символа строки <tex>s</tex>.}}Проблему переполнения при вычислении хешей довольно больших строк можно решить так <tex>{-}</tex> считать хеши по модулю <tex>r=2^{64}</tex> (или <tex>2^{32}</tex>), чтобы модуль брался автоматически при переполнении типов. Для работы алгоритма потребуется считать хеш подстроки <tex>s[i..j]</tex>. Делать это можно следующим образом: Рассмотрим хеш <tex>s[0..j]</tex>: <tex>\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]</tex> Разобьем это выражение на две части:

<tex>\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])</tex> Вынесем из последней скобки множитель <tex>p^{i}</tex>: <tex>\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])</tex> Выражение в первой скобке есть не что иное, как хеш подстроки <tex>s[0..i-1]</tex>, а во второй — хеш нужной нам подстроки <tex>s[i..j]</tex>. Итак, мы получили, что: <tex>\mathrm{hash}(s[0..j]) = \mathrm{hash}(s[0..i-1]) + p^{i}\mathrm{hash}(s[i..j])</tex> Отсюда получается следующая формула для <tex>\mathrm{hash}(s[i..j])</tex>: <tex>\mathrm{hash}(s[i..j]) = (1/p^{i})(\mathrm{hash}(s[0..j]) - \mathrm{hash}(s[0..i-1]))</tex> Однако, как видно из формулы, чтобы уметь считать хеш для всех подстрок начинающихся с <tex>i</tex>, нужно предпосчитать все <tex>p^{i}</tex> для <tex>i \in [0..n - 1]</tex>. Это займет много памяти. Но поскольку нам нужны только подстроки размером <tex>m</tex> <tex>{-}</tex> мы можем подсчитать хеш подстроки <tex>s[0..m-1]</tex>, а затем пересчитывать хеши для всех <tex>i \in [0..n - m]</tex> за <tex>O(1)</tex> следующим образом: <tex>\mathrm{hash}(s[i + 1..i + m - 1]) = (\mathrm{hash}(s[i..i + m - 1]) - p^{m - 1} s[i]) \bmod r</tex>. <tex>\mathrm{hash}(s[i + 1..i + m]) = (p \cdot \mathrm{hash}(s[i + 1..i + m - 1]) + s[i + m]) \bmod r</tex>. Получается : <tex>\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</tex>. ==Решение== ===Алгоритм=Метод хеширования==

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

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

Если требуется найти индексы вхождения нескольких образцов, или сравнить две строки <tex>hash(s[i + 1..i + m - 1]) = hash(s[i..i + m - 1]) - p^{m - 1} </tex> выгоднее будет предпосчитать все степени <tex>p</tex>, а также хеши всех префиксов строки <tex>s[i]</tex>.

===Псевдокод===Приведем пример псевдокода, который находит все вхождения строки <tex>w</tex>в строку <tex>s</tex> и возвращает массив позиций, откуда начинаются вхождения. '''vector<int>''' rabinKarp (s : '''string''', w : '''string'''): '''vector<int>''' answer '''int''' n = s.length '''int''' m = w.length '''int''' hashS = hash(s[i + 10..i + m- 1]) '''int''' hashW = p \cdot hash(sw[i + 10..m - 1]) '''for''' i + = 0 '''to''' n - m '''if''' hashS == hashW answer.add(i) hashS = (p * hashS - 1p<tex>^{m}</tex> * hash(s[i]) + hash(s[i + m])) '''mod''' r <font color=green>/tex/ r — некоторое большое число, p — некоторое просто число</font>. '''return''' answer

Получается : Новый хеш <tex>hash(s[i + 1hashS</tex> был получен с помощью быстрого пересчёта..i + m]) = p \cdot hash(Для сохранения корректности алгоритма нужно считать, что <tex>s[i..i n + m - 1]) - p^{m} s[i] + s[i + m]</tex>{{---}} пустой символ.

==Алгоритм=Время работы===

Есть шаблон - Изначальный подсчёт хешей выполняется за <tex>p[1..O(m])</tex> и строка - <tex>s[1..n]</tex>. Нужно найти все вхождения шаблона в строку.

В начале вычисляются Каждая итерация выполняется за <tex>hashO(s[1..m])</tex> и , В цикле всего <tex>hash(p[n - m + 1..m])</tex>итераций.

Для Итоговое время работы алгоритма <tex>i \in [1..O(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>O(n</tex> <tex>\cdot</tex> <tex>p^{m})</tex>.

==ПсевдокодСравнение с другими алгоритмами == '''RabinKarp''' ('''string''' <tex>s[1..n]</tex>, '''string''' <tex>p[1..m]</tex>)Преимущества: * Быстрая скорость работы — <tex>hp \leftarrow hashO(p[1..n + m])</tex> <tex>h \leftarrow hash(s[1..m])</tex> '''for''' <tex>i \leftarrow 1</tex> '''to''' , где <tex>n - m + 1</tex> '''if''' — длина строки, <tex>h = hp</tex> <tex>answer.add(i)</tex> <tex>h \leftarrow p \cdot h - p^{m} \cdot hash(s[i]) + hash(s[i + m])</tex>— длина образца; '''if''' <tex>answer.size = 0</tex> '''return''' <tex>not</tex> <tex>found</tex> '''else''' '''return''' <tex>answer</tex>* Простая и понятная реализация;

Новый хеш <tex>h</tex> был получен с помощью быстрого пересчёта. Мы считаемНедостатки:* Возможно подобрать входные данные так, что <tex>s[n + 1]</tex> - пустой символ.количество ложных срабатываний будет недопустимо большим;

==Время работыСм. также ==*[[Наивный алгоритм поиска подстроки в строке]]*[[Поиск наибольшей общей подстроки двух строк с использованием хеширования]]

Изначальный подсчёт хешей == Источники информации ==* ''Кормен, Томас Х., Лейзерсон, Чарльз И., Ривест, Рональд Л., Штайн Клиффорд'' '''Алгоритмы: построение и анализ''', 3- <tex>O(m)</tex>е издание. Пер. с англ. — М.:Издательский дом "Вильямс", 2014. — 1328 с.: ил. В цикле всего <tex>n — ISBN 978-5-8459- m + 1</tex> итераций 1794- каждая выполняется за <tex>O2 (1)</tex>рус. Итого - <tex>O(n + m)</tex>— страницы 1036–1041.

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