Поиск по сайту.

Другие алгоритмы.

Поиск в строках, массивах, последовательностях:
Точный поиск подстроки в строке.


'Не такой уж наивный алгоритм'

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

      Будем делать сравнения в следующем порядке: 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 ); 
   }
 }