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