|
Алгоритм Сдвига-Или
Пусть R - битовый массив размера m. Вектор R i - значение массива R после обработки очередного символа. Он содержит информацию обо всех совпадениях префиксов х, которые кончаются на позиции i в тексте ( 0 <= j <= m - 1 ):
R i = 0, если x[ 0, j ] = y[ i - j, i ]
R i = 1, в противоположном случае.
Вектор R i+1 может быть вычислен по R i следующим образом. Для всех R i [j] = 0
R i+1 [ j+1 ] = 0, если x[ j+1 ] = y[ i+1 ],
R i+1 [ j+1 ] = 1 в противоположном случае.
И
R i+1 [ 0 ] = 0, если x[ 0 ] = y[ i+1 ],
R i+1 [ 0 ] = 1 в противоположном случае.
Если R i+1 [ m-1 ] = 0, тогда мы нашли совпадение.
Переход от R i к R i+1 можно очень быстро вычислить следующим образом. Для каждого a из S, пусть S a - битовый массив размера m такой что:
Для 0 <= j <= m - 1, S a = 0 <=> x[ j ] = a
Массив S a обозначает позиции символа a в образце x. Каждый S a может быть вычислен перед процессом поиска. Тогда процесс вычисления R i+1 укорачивается до двух операций: СДВИГА и ИЛИ:
R i+1 = SHIFT( R i ) OR S y[ i+1 ]
Считая длину образца меньше длины компьютерного слова, можно уложиться в O( s + m ) для предобработки и O( n ) для поиска, независимо от длины алфавита и образца.
Реализация на Си
void SO( char *y, char *x, int n, int m )
{
unsigned int j, state, lim, first, initial;
unsigned int T[ASIZE];
int i;
if ( m > WORD ) ERROR( "Use pattern size <= word size" );
/* Preprocessing */
for ( i=0; i < ASIZE; i++ ) T[i] =~0;
lim=0;
for ( i=0, j=1; i < m; i++, j <<=1 ) {
T[x[i]]&=~j;
lim|=j;
}
lim=~( lim >> 1 );
/* Searching */
state=~0;
for ( i=0; i < n; i++ ) {
state = ( state << 1 ) | T[y[i]];
if ( state < lim ) OUTPUT( i-m+1 );
}
}
|
| |