Изменения

Для решения задачи удобно использовать полиномиальный хеш[[Наивный алгоритм поиска подстроки в строке]] работает за <tex>O\left(n^2\right)</tex> в худшем случае — слишком долго. Чтобы ускорить этот процесс, так его легко пересчитывать: можно воспользоваться методом [[Хеш-таблица#Хеширование|хеширования]].{{Определение|definition = Пусть дана строка <tex>s[0..n-1]</tex>. Тогда '''полиномиальным хешем''' (англ. ''polynomial hash'') строки <tex>s</tex> называется число <tex>h = \mathrm{hash}(s[10..n-1]) = ( p^{n - 10} s[10] + ... + p^{0n - 1} s[n-1]) \bmod r</tex>, где <tex>p</tex> {{---}} это — некоторое простое число, а <tex>rs[i]</tex> {<tex>{-}</tex> код <tex>i</tex>-ого символа строки <tex>s</tex>.}}Проблему переполнения при вычислении хешей довольно больших строк можно решить так <tex>{-}} некоторое большое число, для уменьшения числа коллизий (обычно берётся </tex> считать хеши по модулю <tex>r=2^{3264}</tex> (или <tex>2^{6432}</tex>), чтобы модуль брался автоматически при переполнении типов). Стоит обратить внимание, что если 2 строчки имеют одинаковый хэш, то они в большинстве таких случаев равны.

При удалении первого символа строки и добавлении символа в конец Для работы алгоритма потребуется считать хеш новой строки при помощи хеша изначальной строки возможно за подстроки <tex>O(1)s[i..j]</tex>. Делать это можно следующим образом:

Рассмотрим хеш <tex>hash(s[i + 10..i + m - 1j]) = (hash(s[i..i + m - 1]) - p^{m - 1} s[i]) \bmod r</tex>.:

<tex>\mathrm{hash}(s[i 0..j]) = s[0] + p s[1] +...+ p^{i-1} s[i -1] + m]) = (p \cdot hash(^{i} s[i ] + 1..i .+ m p^{j-1} s[j- 1]) + p^{j} s[i + mj]) \bmod r</tex>.

Получается Разобьем это выражение на две части: <tex>hash(s[i + 1..i + m]) = (p \cdot hash(s[i..i + m - 1]) - p^{m} s[i] + s[i + m]) \bmod r</tex>.

Следует учесть, что при получении отрицательного значения необходимо прибавить <tex>r\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[10..mj])</tex> и <tex>hash= (s[0] + p s[1] +...+ p^{i-1} s[i-1]) + p^{i}(s[i] +...m+ p^{j-i-1} s[j-1] + p^{j-i} s[j])</tex>.

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

Для ускорения работы алгоритма оптимально предпосчитать <tex>\mathrm{hash}(s[0..j]) = \mathrm{hash}(s[0..i-1]) + p^{mi}\mathrm{hash}(s[i..j])</tex>.

==Псевдокод== '''RabinKarp''' (s[1..n], p[1..m]) hp = hash(p[1..m]) h = Отсюда получается следующая формула для <tex>\mathrm{hash}(s[1i..mj]) '''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])) mod r '''if''' h < 0 h += r '''if''' answer.size() == 0 '''return''' not found '''else''' '''return''' answer:

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

Изначальный подсчёт хешей выполняется за <tex>O\mathrm{hash}(s[i + 1..i + m- 1])</tex>= (\mathrm{hash}(s[i.. В цикле всего <tex>n i + m - m + 1</tex> итераций, каждая выполняется за <tex>O(1])</tex>. Итоговое время работы алгоритма <tex>O(n + - 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> r \mathrm{hash}(s[i + 1..i + m]) = 2^(p \cdot \mathrm{32hash}, p = 237 </tex>, за <tex> (s </tex> принять [[Слово_Туэi..i + m -Морса | строку Туэ1]) -Морсаp^{i} s[i]]<ref>+ s[http://codeforces.ru/blog/entry/4898 Codeforces: Anti-hash testi + m]</ref> длиной <tex> 1024 ) \bmod r</tex> , то алгоритм находит лишние вхождения почти в половине случаев.

== Примечания Решение==<references></references>

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

Алгоритм начинается с подсчета <tex>\mathrm{hash}(s[0..m-1])</tex> и <tex>\mathrm{hash}(p[0..m-1])</tex>, а также с подсчета <tex>p^{m}</tex>, для ускорения ответов на запрос. Для <tex>i \in [0..n - m]</tex> вычисляется <tex>\mathrm{hash}(s[i..i + m - 1])</tex> и сравнивается с <tex>\mathrm{hash}(p[0..m-1])</tex>. Если они оказались равны, то образец <tex>p</tex> скорее всего содержится в строке <tex>s</tex> начиная с позиции <tex>i</tex>, хотя возможны и ложные срабатывания алгоритма. Если требуется свести такие срабатывания к минимуму или исключить вовсе, то применяют сравнение некоторых символов из этих строк, которые выбраны случайным образом, или применяют явное сравнение строк, как в [[Наивный алгоритм поиска подстроки в строке|наивном алгоритме поиска подстроки в строке]]. В первом случае проверка произойдет быстрее, но вероятность ложного срабатывания, хоть и небольшая, останется. Во втором случае проверка займет время, равное длине образца, но полностью исключит возможность ложного срабатывания.  Если требуется найти индексы вхождения нескольких образцов, или сравнить две строки <tex>{-}</tex> выгоднее будет предпосчитать все степени <tex>p</tex>, а также хеши всех префиксов строки <tex>s</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[0..m - 1]) '''int''' hashW = hash(w[0..m - 1]) '''for''' i = 0 '''to''' n - m '''if''' hashS == hashW answer.add(i) hashS = (p * hashS - p<tex>^{m}</tex> * hash(s[i]) + hash(s[i + m])) '''mod''' r <font color=green>// r — некоторое большое число, p — некоторое просто число</font> '''return''' answer Новый хеш <tex>hashS</tex> был получен с помощью быстрого пересчёта. Для сохранения корректности алгоритма нужно считать, что <tex>s[n + 1]</tex> {{---}} пустой символ. ===Время работы=== Изначальный подсчёт хешей выполняется за <tex>O(m)</tex>.  Каждая итерация выполняется за <tex>O(1)</tex>, В цикле всего <tex>n - m + 1</tex> итераций. Итоговое время работы алгоритма <tex>O(n + m)</tex>. Однако, если требуется исключить ложные срабатывания алгоритма полностью, т.е. придется проверить все полученные позиции вхождения на истинность, то в худшем случае итоговое время работы алгоритма будет <tex>O(n</tex> <tex>\cdot</tex> <tex>m)</tex>. == Сравнение с другими алгоритмами ==Преимущества:* Быстрая скорость работы — <tex>O(n + m)</tex>, где <tex>n</tex> — длина строки, <tex>m</tex> — длина образца;* Простая и понятная реализация; Недостатки:* Возможно подобрать входные данные так, что количество ложных срабатываний будет недопустимо большим; == См. также ==

*[http[Поиск наибольшей общей подстроки двух строк с использованием хеширования]] == Источники информации ==* ''Кормен, Томас Х., Лейзерсон, Чарльз И., Ривест, Рональд Л., Штайн Клиффорд'' '''Алгоритмы://codeforcesпостроение и анализ''', 3-е издание. Пер. с англ. — М.ru/blog/entry/4898 Codeforces: AntiИздательский дом "Вильямс", 2014. — 1328 с.: ил. — ISBN 978-hash test]5-8459-1794-2 (рус.) — страницы 1036–1041.