 |
|
����� � �������, ��������, �������������������:
������ ����� ��������� � ������.
�������� ����� - ������.
������� � ����������� - ������ �.
����������� ����� ��������� ��� �������� ������������� ���������� ��������� �������� � ������� ���������. ������ ����, ����� ��������� ������ ������� �� ������� ������������ � ��������, �� ����� ��������� ������ ��, ������� '����������' �������. ��� ����, ����� ����� ������������� ����� ��������������, ����� ������������ ������� �����������. ��� ������ ������������� ��������� �����������: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 );
}
}