Изменения
Нет описания правки
==Метод хеширования==
Используется полиномиальный хеш {{---}} <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[1..m])</tex> и <tex>hash(p[1..m])</tex>.
== Литература ==
Кормен Т., Лейзерсон Ч., Ривест Р. Алгоритмы: построение и анализ. {{---}} 2-е изд. {{---}} М.: Издательский дом «Вильямс», 2007. {{---}} С. 1296.
==Ссылки==
*[[Наивный алгоритм поиска подстроки в строке]]