Karp-Rabin string searching (Views: 28)
Problem/Question/Abstract: Karp-Rabin string searching Answer: Do you need a fast routine that searches a string within a string? Try the Karp-Rabin algorithm: 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; |