Связь и интернет Архив Программирование
   
Сделать стартовойСделать закладку            
   ПОИСК  
   
Главная / Алгоритмы / Поиск в строках, массивах, последовательностях / Точный поиск подстроки в строке /
8  Perl
8  PHP
8  JavaScript
8  HTML
8  DHTML
8  XML
8  CSS
8  C / C++
8  Pascal и Delphi
8  Турбо Ассемблер
8  MySQL
8  CASE-технологии
8  Алгоритмы
8  Python
8  Обратная связь
8  Гостевая книга
Новости о мире


Алгоритм Хорспула - Программирование от RIN.RU
Алгоритм Хорспула

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


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






 8  Комментарии к статье  8 8  Обсудить в чате

 
  
  
    Copyright ©  RIN 2003 - 2004      * Обратная связь