Частичное совпадение со словом и вычисление
Рис. 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 никогда не возвращается назад, в то время как при прямом поиске после несовпадения просмотр всегда начинается с первого символа слова и поэтому может включать символы, которые ранее уже просматривались. Это может привести к негативным последствиям, если текст читается из вторичной памяти, ведь в этом случае возврат обходится дорого. Даже при буферизованном вводе может встретиться столь большое слово, что возврат превысит емкость буфера.
