DelphiFAQ Home Search:
General :: Programming :: Delphi :: Strings
Algorithms for string handling problems, implemented in Delphi but useful for any procedural language.

Articles:

This list is sorted by recent document popularity (not total page views).
New documents will first appear at the bottom.

Featured Article

Karp-Rabin string searching

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;

Generated 12:01:34 on Jul 27, 2017