Этот алгоритм был создан в 1970 году и получил свое название от имен его разработчиков. Он состоит из двух этапов: подготовительного и основного.

     На подготовительном этапе учитывается структура подстроки. Для этого формируется массив D, в котором учитывается совпадения символов подстроки с началом подстроки следующим образом: нулевой элемент массива D получает значение равное -1. Далее для каждой позиции j, совпадающей с началом подстроки, вычисляется максимальное количество предшествующих ей символов. Если же совпадений нет, то соответствующий элемент массива D равен -1. Размерность массива D равна длине подстроки.

     Теперь рассмотрим основной этап. Поиск начинается со сравнения первого символа строки с первым символом подстроки. В случае несовпадения происходит сдвиг подстроки на количество символов, указанных соответствующим элементом массива D. Если совпадения подстроки со строкой не будет (то есть данной подстроки в строке нет), то программа выйдет из цикла для поиска подстроки, когда i будет равняться длине строки, то есть если ни один символ подстроки не совпадает ни с одним символом строки, то программа выполнит N сравнений, если же совпадения отдельных элементов подстроки(но не всей подстроки со строкой) будут найдены, то в наихудшем случае потребуется N+M сравнений. Если же совпадение подстроки со строкой обнаружится сразу, то потребуется M cравнений.

{kmp.pas

Сайт Algorithm (http://www.algorithm1.narod.ru/)

Автор проекта: Galina}

uses Crt;

const Mmax=100;

          Nmax=10000;

          Esc=#27;

var I, J, K, L, M, N : integer;

      Ch : char;

      P : array [0..Mmax-1] of char;

      S : array [0..Nmax-1] of char;

      D : array [0..Mmax-1] of integer;

begin

  write('Введите строку : ');

  N := 0; Ch := ReadKey;

  While (Ch <> #13) and (N < Nmax-1) do

   begin

    write(Ch);

    S[N] := Ch;

    N:=N+1;

    Ch := ReadKey

   end;

  writeln;

  write('Введите подстроку : ');

  M := 0;

  Ch := ReadKey;

  While (Ch <> #13) and (M < Mmax-1) do

   begin

    write(Ch);

    P[M] := Ch;

    m:=m+1;

    Ch := ReadKey;

   end;

  writeln;

  write('Поиск подстроки : ');

  if Ch=Esc then Exit;

  J := 0; K := -1; D[0] := -1;

  while J < M-1 do

   begin

    while (K >= 0) and (P[J] <> P[K]) do

      K := D[K];

    J:=J+1;

    K:=K+1;

    if P[J]=P[K] then D[J] := D[K]

                      else D[J] := K;

   end;

  J := 0;

  I := 0;

  K := 0;

  while (J < M) and (I < N) do

   begin

     while K<=I do

      begin

       Write(S[K]);

       K:=K+1;

      end;

     while (J >= 0) and (S[I] <> P[J]) do

      J := D[J];

     I:=I+1; J:=J+1;

  end;

  writeln;

  if J = M then writeln('Образец в строке присутствует')

              else writeln('Образец в строке отсутствует');

end.