Изменения

Алгоритм сравнивает символы шаблона (<tex>y</tex>) справа налево, начиная с самого правого, один за другим с символами исходной строки (<tex>x</tex>). В случае несовпадения какого-либо символа (или полного совпадения всего шаблона) он использует две предварительно вычисляемых функций, чтобы сдвинуть позицию для начала сравнения вправо. Пусть <tex>|y|=n</tex> и <tex>|x|=m</tex>. Предположим, что в процессе сравнения возникает несовпадение между символом <tex>x[i]=a</tex> шаблона и символом <tex>y[i+j]=b</tex> исходного текста при проверке в позиции <tex>j</tex>. Тогда <tex>x[i+1 .. m-1]=y[i+j+1 .. j+m-1]=u</tex> и <tex>x[i] \neq y[i+j]</tex>