Алгоритм Кнута-Морриса-Пратта

     Этот алгоритм был получен благодаря глубокому анализу алгоритма Морриса-Пратта. Итак, посмотрим, что еще можно сделать, чтобы увеличить размер сдвига.

     Рассмотрим сравнение на позиции i, где образец x[ 0, m - 1 ] сопоставляется с частью текста y[ i, i + m - 1 ]. Предположим, что первое несовпадение произошло между y[ i + j ] и x[ j ] , где 1 < j < m. Тогда y[ i, i + j - 1 ] = x[ 0, j - 1 ] = u и a = y[ i + j ] =/= x[ j ] = b.

     При сдвиге вполне можно ожидать, что префикс образца u сойдется с каким-нибудь суффиксом подслова текста u. Более того, если мы хотим избежать выявления другого несовпадения ( то есть не тратить на это операцию сравнения ;-) ), буква, находящаяся за префиксом v в образце должна отличаться от b. Наиболее длинный такой префикс v называется границей u ( он встречается по обоим сторонам u ).

     Это приводит к следующему алгоритму: пусть kmp_next[ j ] - длина длиннейшей границы x[ 0, j - 1 ], за которой следует символ c, отличающийся от x[ j ]. Тогда после сдвига мы можем возобновить сравнения между символами y[ i + j ] и x[ j - kmp_next[ j ] ] без возможной потери местонахождения образца. Таблица kmp_next может быть вычислена за O( m ) перед поиском через применение этого же алгоритма поиска к самому образцу ( т.е y = x ). При этом максимальное количество сравнений для одного символа текста - logФ( m ), где Ф - золотое сечение: ( корень из 5 + 1 ) / 2.

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


   /* Preprocessing */



void PRE_KMP( char *x, int m, int kmp_next[] ) {

 int i, j; 

 

 i=0; 

 j=kmp_next[0]=-1; 

 while ( i < m ) {

    while ( j > -1 && x[ i ] != x[ j ] ) j=kmp_next[ j ]; 

   i++; 

   j++; 

   if ( x[ i ] == x[ j ] ) kmp_next[i]=kmp_next[j]; 

      else kmp_next[ i ] = j; 

   }

}



void KMP( char *x, char *y, int n, int m ) {

   int i, j, kmp_next[XSIZE]; 

   

   /* Preprocessing */

   PRE_KMP(x, m, kmp_next ); 

   

   /* Searching */

   

   i=j=0; 

   while ( i < n ) {

      while ( j > -1 && x[ j ] != y[ i ] ) j = kmp_next[ j ];

     i++; 

     j++; 

     if ( j >= m ) {

        OUTPUT( i - j ); 

       j = kmp_next[ j ]; 

       }

   }

}


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

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

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