Хеширование может позволить нам избежать квадратичного количества сравнений символов в обычных ситуациях. Вместо того, чтобы проверять каждую позицию на предмет соответствия с образцом, мы можем проверять только те, которые 'напоминают' образец. Для того, чтобы легко устанавливать явное несоответствие, будем использовать функцию хеширования. Она должна удовлетворять следующим требованиям:

     1. Легко вычисляться.

     2. Как можно лучше различать несовпадающие строки.

     3. hash( y[ i+1 , i+m ] ) должна легко вычисляться по hash( y[ i , i+m-1 ] ):

hash( y[ i+1 , i+m ] ) = rehash( y[ i ], y[ i+m ], hash( y[ i , i+m-1]).

     Пусть наша функция будет определена для слова w, например, следующим образом:

hash( w[ 0 , m-1 ] ) = ( w[0] * 2 m-1 + w[1] * 2 m-2 + ... + w[m-1] ) mod q,

где q - большое число. Тогда

rehash( a, b, h ) = (( h - a * 2 m-1 ) * 2 + b) mod q.

     Во время поиска х будем сравнивать hash( x ) с hash( y[ i, i+m-1 ] ) для i от 0 до n-m включительно. Если обнаруживаем совпадение, то проверяем посимвольно.

     Наихудший случай O( n * m ) встретится, например, при поиске a m в a n .