Delphi World - Точный поиск подстроки в строке - Алгоритм Хорспула
Delphi World - это проект, являющийся сборником статей и малодокументированных возможностей  по программированию в среде Delphi. Здесь вы найдёте работы по следующим категориям: delphi, delfi, borland, bds, дельфи, делфи, дэльфи, дэлфи, programming, example, программирование, исходные коды, code, исходники, source, sources, сорцы, сорсы, soft, programs, программы, and, how, delphiworld, базы данных, графика, игры, интернет, сети, компоненты, классы, мультимедиа, ос, железо, программа, интерфейс, рабочий стол, синтаксис, технологии, файловая система...
Точный поиск подстроки в строке - Алгоритм Хорспула

Автор: 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 ];
 }
}
Проект Delphi World © Выпуск 2002 - 2017
Автор проекта: Эксклюзивные курсы программирования