Karp-Rabin string searching

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;