Хеширование может позволить нам избежать квадратичного количества сравнений символов в обычных ситуациях. Вместо того, чтобы проверять каждую позицию на предмет соответствия с образцом, мы можем проверять только те, которые 'напоминают' образец. Для того, чтобы легко устанавливать явное несоответствие, будем использовать функцию хеширования. Она должна удовлетворять следующим требованиям: Легко вычисляться. Как можно лучше различать несовпадающие строки. 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 ); } }  8  Комментарии к статье  8 8  Обсудить в чате