Изменения
→Метод хеширования
==Метод хеширования==
[[Наивный алгоритм поиска подстроки в строке]] работает за <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>.
