Delphi World - Точный поиск подстроки в строке - Не такой уж наивный алгоритм

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

Точный поиск подстроки в строке - Не такой уж наивный алгоритм

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

Будем делать сравнения в следующем порядке: 1, 2, ... , m - 2, m - 1, 0.

Для каждой попытки совмещения x с y[ i , i + m - 1 ]:

если x[ 0 ] = x[ 1 ] и x[ 1 ] =/= y[ i + 1 ] или если x[ 0 ] =/= x[ 1 ] и x[ 1 ] = y[ i + 1 ] образец можно сдвинуть на две позиции или, в противоположном случае, на одну.

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

void NSN( char *x, char *y, int n, int m )
 {
 int i,  k,  l; 
 char secondch, firstch, *thirdch; 
 
 if ( x[ 0 ] == x[ 1 ] ) {
    k = 2; 
   l = 1; 
 }
 else {
    k = 1; 
   l = 2; 
 }
 
/* Searching */
i = 0;
firstch = x[ 0 ]; 
secondch = x[ 1 ]; 
thirdch = &x[ 2 ]; 
while ( i <= n - m )
   if ( y[ i + 1 ] != secondch ) i+=k;
   else {
      if ( memcmp(&y[ i + 2 ], thirdch, m - 2 ) == 0
	   && y[ i ] == firstch ) OUTPUT( i ); 
   }
 }