Изменения

[[Наивный алгоритм поиска подстроки в строке]] работает за <tex>O\left(n^2\right)</tex> в худщем худшем случае - — слишком долго. Чтобы ускорить этот процесс, можно воспользоваться методом [[Хеш-таблица#Хеширование|хеширования]].

|definition = Пусть дана строка <tex>s[10..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]</tex>, где <tex>p</tex> - — некоторое натуральное простое число, а <tex>s[i]</tex> <tex>{- }</tex> код <tex>i</tex>-ого символа строки <tex>s</tex>.

Проблему переполнения при вычислении хешей довольно больших строк можно решить так: будем <tex>{-}</tex> считать хеши по модулю <tex>r=2^{64}</tex> - некоторому большому числу (будем брать или <tex>r =2^{6432}</tex>), чтобы модуль брался автоматически при переполнении типов). Число <tex>p</tex> для их подсчета должно быть, во-первых, больше кода самого большого символа в строках, а во-вторых, взаимно простым с модулем (в нашем случае — с 2^{64}, т.е. оно должно быть нечетным).

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

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

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

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

Для ускорения работы алгоритма оптимально предпосчитать Выражение в первой скобке есть не что иное, как хеш подстроки <tex>p^{m}s[0..i-1]</tex>, а во второй — хеш нужной нам подстроки <tex>s[i..j]</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 = \mathrm{hash}(s[10..mj]) '''int''' hashW = \mathrm{hash}(ws[10..m]) '''for''' i = 1 '''to''' n - m + 1 '''if''' hashS == hashW answer.add(i]) hashS = (+ p * hashS - p<tex>^{mi}</tex> * \mathrm{hash}(s[i..j]) + hash(s[i + m])) mod r <font color=green>//r - некоторое большое число, p - некоторое просто число</fonttex> '''return''' answer

Новый хеш <tex>hashS</tex> был получен с помощью быстрого пересчёта. Для сохранения корректности алгоритма нужно считать, что Отсюда получается следующая формула для <tex>\mathrm{hash}(s[n + 1i..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>O(m)</tex>.  Каждая итерация выполняется за <tex>O({-}</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]) = (p \cdot \mathrm{hash}(s[i..i + m - 1]) - p^{mi} s[i] + s[i + m]) \bmod r</tex>.

== Надёжность =Алгоритм===Если количество подстрок данной строки превышает количество хешей, то наступление [[Разрешение_коллизий | коллизий]] неизбежно. Но даже при относительно небольших строках вероятность коллизий может быть [[Хеш-таблица#Введение | высока]], не говоря уже о способах составления специальных строк, где алгоритм на хешах выдаёт частые ложные срабатывания.

Например, возьмем за Алгоритм начинается с подсчета <tex>S</tex> \mathrm{hash}(s[[Слово_Туэ-Морса | строку Туэ-Морса]]<ref>[http://codeforces0..ru/blog/entry/4898 Codeforces: Antim-hash test1])</reftex> длиной и <tex>2^\mathrm{khash}(p[0..m-1])</tex>, а также с подсчета <tex>r = 2p^{64m}</tex>, <tex>p</tex> - любое просто числодля ускорения ответов на запрос.

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

ПокажемЕсли требуется найти индексы вхождения нескольких образцов, что при или сравнить две строки <tex>k = 10</tex>, <tex>\mathrm{hash}(S_k) = \mathrm{hash-}(not S_k)</tex>. Ведь если это так, то сами по себе выгоднее будет предпосчитать все степени <tex>S_kp</tex> и , а также хеши всех префиксов строки <tex>not S_ks</tex> встретятся в б''о''льших строках много-много раз.

Разберемся===Псевдокод===Приведем пример псевдокода, что значит который находит все вхождения строки <tex>w</tex> в строку <tex>s</tex>\mathrm{и возвращает массив позиций, откуда начинаются вхождения. '''vector<int>''' rabinKarp (s : '''string''', w : '''string'''): '''vector<int>''' answer '''int''' n = s.length '''int''' m = w.length '''int''' hashS = hash}(S_ks[0..m - 1]) '''int''' hashW = \mathrm{hash}(not S_kw[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 <texfont color=green>A// r — некоторое большое число, p — некоторое просто число</texfont> и '''return''' answer Новый хеш <tex>BhashS</tex> нули и единицы в коэффициентах многочлена - тем самым мы просто сократим обе части на был получен с помощью быстрого пересчёта. Для сохранения корректности алгоритма нужно считать, что <tex>\sum_{i=0}^{i<2^k} 65 \cdot p^is[n + 1]</tex>{{---}} пустой символ.

Что такое <tex>\mathrm{hash}(S_k) - \mathrm{hash}(not S_k)</tex>? Нетрудно сообразить, что эта величина есть: <tex>T = p^{0} - p^{1} - p^{2} + p^{3} - p^{4} + p^{5} + p^{6} - p^{7} ... \pm p^{2^k - 1}</tex>. То есть это знакопеременная сумма степеней <tex>p</tex>, где знаки чередуются по тому же правилу, что и символы в строке.==Время работы===

Будем последовательно выносить из этой суммы множители Изначальный подсчёт хешей выполняется за скобку:<tex>O(m)</tex>.

Каждая итерация выполняется за <tex>T = O(p^{1} - 1)( </tex>, В цикле всего <tex>n - p^{0} m + p^{2} + p^{4} - p^{6} + p^{8} - p^{10} - p^{12} + p^{14} ...) = 1</tex>итераций.

Итоговое время работы алгоритма <tex> = O(p^{1} - 1)(p^{2} - 1)(p^{0} - p^{4} - p^{8} n + p^{12} ...) = ... = (p^{1} - 1m)(p^{2} - 1)(p^{4} - 1) ... (p^{2^{k-1}} - 1).</tex>.

А теперь самое главное - эта величина по модулю Однако, если требуется исключить ложные срабатывания алгоритма полностью, т.е. придется проверить все полученные позиции вхождения на истинность, то в худшем случае итоговое время работы алгоритма будет <tex>O(n</tex> <tex>\cdot</tex> <tex>2^{64}m)</tex> моментально занулится. Почему?

Давайте поймём, на какую максимальную степень двойки делится каждая из <tex>k - 1</tex> скобок. Заметим, что == Сравнение с другими алгоритмами ==Преимущества:* Быстрая скорость работы — <tex>O(i n + 1m)</tex>-ая скобка <tex>p^{2^{i + 1}}  -  1 = (p^{2i}  -  1)(p^{2i}  +  1)</tex> делится на <tex>i</tex>-ую и ещё на какое-то чётное число <tex>p^{2i}  +  1</tex>. Это означает, что если где <tex>i</tex>-ая скобка делится на <tex>2^rn</tex>— длина строки, то <tex>(i + 1)m</tex>-ая скобка делится по меньшей мере на <tex>2^{r + 1}</tex>.— длина образца;* Простая и понятная реализация;

Вот и выходитНедостатки:* Возможно подобрать входные данные так, что <tex>(p^1 - 1)(p^2 - 1)(p^4 - 1)...(p^{2k - 1}  -  1)</tex> делится по меньшей мере на <tex>2 \cdot 2^2 \cdot 2^3 \cdot ...  =  2^{k(k - 1) / 2}</tex>. Значит достаточно взять <tex>k >= 12</tex>, чтобы в рассматриваемой строке было очень много различных подстрок, чьи хеши совпадут.количество ложных срабатываний будет недопустимо большим;