Изменения

Для <tex>i \in [1..n - m + 1]</tex> вычисляется <tex>hash(s[i..i + m - 1])</tex> и сравнивается с <tex>hash(p[1..m])</tex>. Если они оказались равны, то считается, что подстрока образец <tex>p</tex> входит содержится содержится в строку строке <tex>s</tex> (, начиная с позиции <tex>i</tex>) , но в этом случае возможны ложные срабатывания алгоритма. Если требуется свести такие срабатывания к минимуму или проверяетсяисключить вообще, что подстрока является шаблономто применяют сравнение некоторых символов из этих строк, которые выбраны случайным образом, или применяют полное посимвольное сравнение, для этого выбираются как в [[Наивный алгоритм поиска подстроки в строке|наивном алгоритме поиска подстроки в строке]]. В первом случае проверка произойдет быстрее, но вероятность ложного срабатывания останется хоть и сравниваются случайные символы из строкнебольшая, во втором случае проверка займет время равное длине образца, но исключит возможность ложного срабатывания.