[Home]
[Chapter]
[Contents]
[Previous Algorithm]
[Next Algorithm]


Knuth-Morris-Pratt text searching


function search( pat: PATTERN; text: TEXT ): 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;

C source (712.srch.c) Pascal source (712.srch.p)



© Addison-Wesley Publishing Co. Inc.