Изменения
→Метод хеширования
|definition = Пусть дана строка <tex>s[0..n-1]</tex>. Тогда '''полиномиальным хешем''' строки <tex>s</tex> называется число <tex>h = \mathrm{hash}(s[0..n-1]) = p^{n - 1} s[0] + ... + p^{0} s[n-1]</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>O(1)</tex>:
