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

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

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

Рассмотрим сравнение на позиции 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 ]; 
       }
   }
}
Проект Delphi World © Выпуск 2002 - 2017
Автор проекта: Эксклюзивные курсы программирования