Изменения
→Псевдокод
'''if''' hashS == hashW
answer.add(i)
hashS = (p * hashS - p<tex>^{m}</tex> * hash(s[i]) + hash(s[i + m])) '''mod ''' r <font color=green>//r - — некоторое большое число, p - — некоторое просто число</font>
'''return''' answer
Новый хеш <tex>hashS</tex> был получен с помощью быстрого пересчёта. Для сохранения корректности алгоритма нужно считать, что <tex>s[n + 1]</tex> {{---}} пустой символ.
Рекомендуется брать <tex>r = 2^{64}</tex> (чтобы модуль брался автоматически при переполнении типов), а <tex>p</tex> - больше кода самого большого символа в строках.
==Время работы==
