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

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

   


Назад К началу странички

Вверх по каталогу
Вперед



Построение автомата Алгоритм грубой силы
Алгоритм Боуера-Мура Алгоритм Хорспула
Алгоритм Карпа-Рабина Алгоритм Кнута-Морриса-Пратта
Алгоритм Морриса-Пратта Не такой уж наивный алгоритм
Алгоритм Сдвига-Или