{An explanation of the Knuth-Morris-Pratt algorithm can be found in the Independent-SortSearch Section}
program knuth_morris_pratt;
{Author: unknown; main program by Peter Palfrader <weasel@netalive.org>}

const
   MAXPATLEN = 255; {maximal pattern length}
   
function search( pat, text: string ): integer;
var next      : array [1..MAXPATLEN] of integer;
   i, j, m, n : integer;
   found      : boolean;
	      
procedure preprocpat;

var k, l : integer;
begin	 
   m := length(pat);
   l := 1;
   k := 0; next[1] := 0;
   repeat begin
      if (k=0) or (pat[l]=pat[k]) then begin
	 l := l+1; k := k+1;
	 if pat[k]=pat[l] then next[l] := next[k]
	 else                  next[l] := k;
      end
      else k := next[k];
   end
   until ( l > m );
end;

begin
   found := FALSE; search := 0;
   m := length(pat);
   if m=0 then begin
      search := 1;  found := TRUE; end;
   preprocpat;

   n := length(text);
   j := 1; i := 1;
   while not found and (i <= n) do begin
      if (j=0) or (pat[j] = text[i]) then begin
	 i := i+1; j := j+1;
	 if j > m then begin
	    search := i-j+1;
	    found := TRUE;
	 end;
      end
      else j := next[j];
   end;
end;









var
   text	   : string;
   pattern : string;

begin
   text    := 'the caterpillar';
   pattern := 'pill';

   writeln('Knuth-Morris-Pratt Search');
   writeln('Text            : ',text);
   writeln('Pattern         : ',pattern);
   writeln('Hit at position : ', search(pattern, text));
end.