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


Karp-Rabin string searching


function search( pat: PATTERN; text: TEXT ): integer; const B = 131; var hpat, htext, Bm, j, m, n: integer; found: boolean; begin found := FALSE; search := 0; m := length(pat); if m=0 then begin search := 1; found := TRUE; end; Bm := 1; hpat := 0; htext := 0; n := length(text); if n >= m then {*** preprocessing ***} for j := 1 to m do begin Bm := Bm*B; hpat := hpat*B + ord(pat[j]); htext := htext*B + ord(text[j]); end; j := m; {*** search ***} while not found do begin if (hpat = htext) and (pat = substr(text,j-m+1,m)) then begin search := j-m+1; found := TRUE; end; if j < n then begin j := j+1; htext := htext*B - ord(text[j-m])*Bm + ord(text[j]); end else found := TRUE; end; end;

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



© Addison-Wesley Publishing Co. Inc.