Изменения

Для <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>, но в этом случае возможны ложные срабатывания алгоритма. Если требуется свести такие срабатывания к минимуму или исключить вообще, то применяют сравнение некоторых символов из этих строк, которые выбраны случайным образом, или применяют полное посимвольное явное сравнениестрок, как в [[Наивный алгоритм поиска подстроки в строке|наивном алгоритме поиска подстроки в строке]]. В первом случае проверка произойдет быстрее, но вероятность ложного срабатывания останется хоть и небольшая, во втором случае проверка займет время равное длине образца, но исключит возможность ложного срабатывания.