{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.