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;
|