Шпоры по МПиПА / Строки / Алгоритм Кнута Морриса и Пратта / Pascal / Исходник / KMP

Program KMP;
const
Nmax = 10000;
type
MyString = array[0..Nmax-1] of char;
var
s: MyString;
p: MyString;

function KMPSearch(var str, substr : MyString ) : integer;
var i, j, k, M, N: integer;
d: array[0..Nmax-1] of integer;
begin
N := Length(str);
M := Length(substr);
if ( N = 0 ) then begin write('Wrong string: '); KMPSearch := -1; exit; end;
if ( M = 0 ) then begin write('Wrong substring: '); KMPSearch := -1; exit; end;

j:=0;
k:=-1;
d[0]:=-1;
while j<(M-1) do begin
while(k>=0) and (substr[j]<>substr[k]) do k:=d[k];
j:=j+1;
k:=k+1;
if substr[j]=substr[k] then
d[j]:=d[k]
else
d[j]:=k;
end;

i:=0;
j:=0;
while (j<M) and (i<N) do begin
while (j>=0) and (str[i]<>substr[j]) do j:=d[j];
i:=i+1;
j:=j+1;
end;

if j=M then KMPSearch := i-M
else KMPSearch := -1;
end;

begin
Writeln('Knuth Morris Pratt Algoritm.');
Write('String: '); Readln(s);
Write('Substring: '); Readln(p);
Write('Result: '); writeln( KMPSearch(s,p) );
Writeln('Press any key to continue...');
Readln;
end.