Быстрый поиск

     Сдвиг плохого символа, используемый в алгоритме Боуера - Мура, не очень эффективен для маленького алфавита, но, когда размер алфавита большой по сравнению с длиной образца, как это часто имеет место с таблицей ASCII и при обычном поиске в текстовом редакторе, он становится чрезвычайно полезен. Использование в алгоритме только его одного может быть весьма эффективным.

     После попытки совмещения x и y [ i , i + m - 1 ], длина сдвига - не менее 1. Таким образом, символ y [ i + m ] обязательно будет вовлечен в следующую попытку, а значит, может быть использован в текущей попытке для сдвига плохого символа. Модифицируем функцию плохого символа, чтобы принять в расчет последний символ х:

bc[ a ] = min { j | 0 <= j <= m и x[ m - 1 - j ] = a }, если a встречается в x,

bc[ a ] = m в противоположном случае.

     Сравнения текста и образца могут производиться в любом порядке. Несмотря на маловероятный худший случай, алгоритм демонстрирует прекрасное поведение на практике.

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


   void QS( char *y, char *x, int n, int m)

{

 int i, qs_bc[ ASIZE ];

 

 /* Preprocessing */

 for ( i = 0; i < ASIZE; i++ ) qs_bc[ i ] = m + 1;

 for ( i = 0; i < m; i ++ ) qs_bc[ x[ i ] ] = m - 1;

 

 /* Searching */

 i = 0; 

 while ( i <= n - m ) {

    if ( memcmp( &y[ i ], x, m ) == 0 ) OUTPUT( i );

   i += qs_bc[ y[ i + m ] ];             /* shift */

 }

}


Назад К началу странички

Вверх по каталогу 		Вперед

Построение автомата Алгоритм грубой силы
Алгоритм Боуера-Мура Алгоритм Хорспула
Алгоритм Карпа-Рабина Алгоритм Кнута-Морриса-Пратта
Алгоритм Морриса-Пратта Не такой уж наивный алгоритм
Алгоритм Сдвига-Или