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

Автор: Thierry Lecroq
Перевод: Кантор И.

Сдвиг плохого символа, используемый в алгоритме Боуера - Мура, не очень эффективен для маленького алфавита, но, когда размер алфавита большой по сравнению с длиной образца, как это часто имеет место с таблицей 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 - i;
 
 /* Searching */
 i = 0; 
 while ( i <= n - m ) {
    if ( memcmp( &y[ i ], x, m ) == 0 ) OUTPUT( i );
   i += qs_bc[ y[ i + m ] ];             /* shift */
 }
}
Проект Delphi World © Выпуск 2002 - 2024
Автор проекта: USU Software
Вы можете выкупить этот проект.