:: алгоритмы и методы :: :: олимпиадные задачи :: :: связь :: :: о сайте :: :: форум ::
Путь: Поиск. Строки и последовательности » Точный подстроки в строке » Алгоритм Хорспула
  Алгоритм Хорспула

Автор: Thierry Lecroq
Перевод с английского - Кантор И.

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

     В 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 ];
 }
}

Обсудить на форуме »
На правах рекламы
Оптом igbt транзисторы.
Нулевой баланс - бухгалтерское обслуживание самара; ведение бухгалтерии.
Работа киев для профессионалов работа киев бесплатно на нашем сайте.
Широкий ассортимент товара спальни самая лучшая мебель.