Алгоритм Хорспула

     Этот алгоритм - некоторое упрощение стандартного Боуера - Мура.

     В 1980 году Хорспул ( Horspool ) предложил использовать только сдвиг по самому правому символу для вычисления сдвига в алгоритме Боуера - Мура.

     Получившийся алгоритм имеет квадратичную скорость в худшем случае,но было доказано, что среднее число сравнений на символ текста находится между 1 / |s| и 2 / ( |s| + 1 ).

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


   void HORSPOOL( char *y , сhar *x ,int n , int m )

{

 int a, i, j, bm_bc[ ASIZE ];

 char ch, lastch;

 

 /* Preprocessing */

 for ( a=0; a < ASIZE; a++ ) bm_bc[ a ] = m;

 for ( j=0; j < m-1; j++ ) bm_bc[ x[ j ] ] = m - j - 1;

 

 /* Searching */

 lastch = x[ m-1 ];

 i = 0;

 while ( i <= n-m ) {

     ch = y[ i + m - 1 ];

    if ( ch == lastch )

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

    i += bm_bc[ ch ];

 }

}


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

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

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