Изменения

Проблему переполнения при вычислении хешей довольно больших строк можно решить так: будем считать хеши по модулю <tex>r</tex> - некоторому большому числу (будем брать <tex>r =2^{64}</tex>, чтобы модуль брался автоматически при переполнении типов). Число <tex>p</tex> для их подсчета должно быть, во-первых, больше кода самого большого символа в строках, а во-вторых, взаимно простым с модулем (в нашем случае — с 2^{64}, т.е. оно должно быть нечетным).

<tex>\mathrm{hash}(s[i + 1..i + m - 1]) = (\mathrm{hash}(s[i..i + m - 1]) - p^{m - 1} s[i]) \bmod r</tex>.