Изменения

Получается : <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>.

Алгоритм начинается с подсчета <tex>\mathrm{hash}(s[1..m])</tex> и <tex>\mathrm{hash}(p[1..m])</tex>.

Для ускорения работы алгоритма оптимально предпосчитать <tex>p^{m}</tex>.

Приведем пример псевдокода, который находит все вхождения строки <tex>w</tex> в строку <tex>s</tex> и возвращает массив позиций, откуда начинаются вхождения.

'''vector<int>''' rabinKarp (s : '''string''', w : '''string'''):

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

Изначальный подсчёт хешей выполняется за <tex>O(m)</tex>.

Итоговое время работы алгоритма <tex>O(n + m)</tex>.

Если количество подстрок данной строки превышает количество хешей (а это выполняется тогда, когда длина строки больше <tex>r</tex>, так как количество различных значений полиномиального хеша совпадает с <tex>r</tex>), то наступление [[Разрешение_коллизий | коллизий]] неизбежно. Но даже при относительно небольших строках вероятность коллизий может быть [[Хеш-таблица#Введение | высока]], не говоря уже о способах составления специальных строк, где алгоритм на хешах выдаёт частые ложные срабатывания.