Изменения

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