Изменения
→Метод хеширования
}}
Проблему переполнения при вычислении хешей довольно больших строк можно решить так: будем считать хеши по модулю <tex>r</tex> - некоторому большому числу (будем брать <tex>r =2^{64}</tex>, чтобы модуль брался автоматически при переполнении типов). Число <tex>p</tex> для их подсчета должно быть, во-первых, больше кода самого большого символа в строках, а во-вторых, взаимно простым с модулем (в нашем случае — с 2^{64}, т.е. оно должно быть нечетным).
Полиномиальный хеш именно с убывающими степенями <tex>p</tex> позволяет нам, зная хеш строки, посчитать хеш строки, образованной удалением первого символа и добавлением символа в конец, за <tex>O(1)</tex>:
<tex>\mathrm{hash}(s[i + 1..i + m - 1]) = (\mathrm{hash}(s[i..i + m - 1]) - p^{m - 1} s[i]) \bmod r</tex>.
<tex>\mathrm{hash}(s[i + 1..i + m]) = (p \cdot \mathrm{hash}(s[i + 1..i + m - 1]) + s[i + m]) \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>.
==Алгоритм==
