Изменения
Нет описания правки
==Метод хеширования==
[[Наивный алгоритм поиска подстроки в строке]] работает за <tex>O\left(n^2\right)</tex> в худшем случае - — слишком долго. Чтобы ускорить этот процесс, можно воспользоваться методом [[Хеш-таблица#Хеширование|хеширования]].
{{Определение
|definition = Пусть дана строка <tex>s[1..n]</tex>. Тогда полиномиальным хешем строки <tex>s</tex> называется число <tex>h = \mathrm{hash}(s[1..n]) = p^{n - 1} s[1] + ... + p^{0} s[n]</tex>, где <tex>p</tex> - — некоторое натуральное число, а <tex>s[i]</tex> - код <tex>i</tex>-ого символа строки <tex>s</tex>.
}}
Проблему переполнения при вычислении хешей довольно больших строк можно решить так: будем считать хеши по модулю <tex>r</tex> - — некоторому большому числу (будем брать <tex>r =2^{64}</tex>, чтобы модуль брался автоматически при переполнении типов). Число <tex>p</tex> для их подсчета должно быть, во-первых, больше кода самого большого символа в строках, а во-вторых, взаимно простым с модулем (в нашем случае — с <tex>2^{64}</tex>, т.е. оно должно быть нечетным).
Использование полиномиального хеша именно с убывающими степенями <tex>p</tex> позволяет нам, зная хеш некоторой строки, посчитать хеш строки, образованной удалением первого символа и добавлением символа в конец, за <tex>O(1)</tex>:
Если количество подстрок данной строки превышает количество хешей (а это выполняется тогда, когда длина строки больше <tex>r</tex>, так как количество различных значений полиномиального хеша совпадает с <tex>r</tex>), то наступление [[Разрешение_коллизий | коллизий]] неизбежно. Но даже при относительно небольших строках вероятность коллизий может быть [[Хеш-таблица#Введение | высока]], не говоря уже о способах составления специальных строк, где алгоритм на хешах выдаёт частые ложные срабатывания.
Например, возьмем за <tex>S</tex> [[Слово_Туэ-Морса | строку Туэ-Морса]]<ref>[http://codeforces.ru/blog/entry/4898 Codeforces: Anti-hash test]</ref> длиной <tex>2^{k}</tex>, <tex>r = 2^{64}</tex>, <tex>p</tex> - — любое просто число.
Обозначим за <tex>S_k</tex> строку <tex>S</tex> для фиксированного <tex>k</tex> , а за <tex>S'_k</tex> инвертированную строку <tex>S</tex>.
Покажем, что при <tex>k = 10</tex>, <tex>\mathrm{hash}(S_k) = \mathrm{hash}(S'_k)</tex>. Ведь если это так, то сами по себе <tex>S_k</tex> и <tex>S'_k</tex> встретятся в б''о''льших строках много-много раз.
Разберемся, что значит <tex>\mathrm{hash}(S_k) = \mathrm{hash}(S'_k)</tex>. Можно смело заменить коды символов на нули и единицы в коэффициентах многочлена - — тем самым мы просто сократим обе части на <tex>\sum\limits_{i=0}^{2^k - 1} 65 \cdot p^i</tex>.
Что такое <tex>\mathrm{hash}(S_k) - \mathrm{hash}(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(n + m)</tex>, где <tex>n</tex> - длина строки, <tex>m</tex> - длина образца.
* Простая и понятная реализация.
=== Недостатки ===
