Структуры и алгоритмы обработки данных

       

Частичное совпадение со словом и вычисление




Рис. 2.2. Частичное совпадение со словом и вычисление d j.

то считается dj=-1, что указывает на сдвиг на целое¦ слово относительно его текущей позиции. Следующая программа демонстрирует КМП-алгоритм.

Program KMP;

const

Mmax = 100; Nmax = 10000;

var

        i, j, k, M, N: integer;

        p: array[0..Mmax-1] of char; {слово}

        s: array[0..Mmax-1] of char; {текст}

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

begin



{Ввод текста s и слова p}

Write('N:'); Readln(N);

Write('s:'); Readln(s);

Write('M:'); Readln(M);

Write('p:'); Readln(p);

{Заполнение массива d}

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;

{Поиск слова p в тексте s}

i:=0; j:=0;

while (j<M) and (i<N) do begin

         while (j>=0) and (s[i]<>p[j]) do j:=d[j]; {Сдвиг слова}

          i:=i+1; j:=j+1;

end;

{Вывод результата поиска}

if j=M then Writeln('Yes') {найден }

else Writeln('No'); {не найден}

Readln;

end.

Точный анализ КМП-поиска, как и сам его алгоритм, весьма сложен. Его изобретатели доказывают, что требуется порядка M+N сравнений символов, что значительно лучше, чем M*N сравнений из прямого поиска. Они так же отмечают то положительное свойство, что указатель сканирования i никогда не возвращается назад, в то время как при прямом поиске после несовпадения просмотр всегда начинается с первого символа слова и поэтому может включать символы, которые ранее уже просматривались. Это может привести к негативным последствиям, если текст читается из вторичной памяти, ведь в этом случае возврат обходится дорого. Даже при буферизованном вводе может встретиться столь большое слово, что возврат превысит емкость буфера.



Содержание раздела