Mega Code Archive
Karp-rabin string searching
<![CDATA[
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;
]]>