Автор: Thierry Lecroq
Перевод: Кантор И.

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

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 .

Реализация на Си

/* 
   Here all the modulo multiplications by 2 are made using shifts. 
   So q = max integer avianable
*/

#define REHASH( a, b, h ) ((( h - a * d ) << 1 ) + b )

void KR( char *y, char *x, int n, int m ) {
 int hy, hx, d, i;
 
 /*
   Preprocessing
   computes d = 2^( m-1 ) with the left-shift operator
  */
  d = 1;
  for ( i = 1; i < m; i++ ) d = ( d << 1 );
  
  hy = hx = 0;
  for ( i = 0; i < m; i++) {
      hx = ( ( hx << 1 ) + x[i] ); 
     hy = ( ( hy << 1 ) + y[i] );
   }
   
 /* Searching */
 
 for ( i=m; i < n; i++ ) {
      if ( hy == hx && memcmp( &y[ i-m-1 ], x, m ) == 0 ) OUTPUT( i-m ); 
     hy = REHASH( y[i-m], y[i], hy ); 
    }
  }