Author: William Gerbert Karp-Rabin string searching Answer: Do you need a fast routine that searches a string within a string? Try the Karp-Rabin algorithm: 1 function search(pat: PATTERN; Text: Text): integer; 2 const 3 b = 131; 4 var 5 hpat, htext, Bm, j, m, n: integer; 6 found: Boolean; 7 begin 8 found := False; 9 search := 0; 10 m := length(pat); 11 if m = 0 then 12 begin 13 search := 1; 14 found := true 15 end; 16 17 Bm := 1; 18 hpat := 0; 19 htext := 0; 20 n := length(Text); 21 if n >= m then 22 {*** preprocessing ***} 23 for j := 1 to m do 24 begin 25 Bm := Bm * b; 26 hpat := hpat * b + ord(pat[j]); 27 htext := htext * b + ord(Text[j]) 28 end; 29 30 j := m; 31 {*** search ***} 32 while not found do 33 begin 34 if (hpat = htext) and (pat = substr(Text, j - m + 1, m)) then 35 begin 36 search := j - m + 1; 37 found := true 38 end; 39 if j < n then 40 begin 41 j := j + 1; 42 htext := htext * b - ord(Text[j - m]) * Bm + ord(Text[j]) 43 end 44 else 45 found := true 46 end 47 end;