DelphiFAQ Home Search:

Karp-Rabin string searching

 

comments3 comments. Current rating: 4 stars (2 votes). Leave comments and/ or rate it.

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;

Comments:

2007-01-27, 03:32:13
from Sweden  
rating
<Text>
2007-08-15, 13:23:40
anonymous from Turkey  
serkan akbaba


Keywords:
2012-12-19, 09:45:58
[hidden] from Indonesia  
rating
please help me..
give me full source tihis source code for a rabin karp algorithm


Keywords:

 

 

NEW: Optional: Register   Login
Email address (not necessary):

Rate as
Hide my email when showing my comment.
Please notify me once a day about new comments on this topic.
Please provide a valid email address if you select this option, or post under a registered account.
 

Show city and country
Show country only
Hide my location
You can mark text as 'quoted' by putting [quote] .. [/quote] around it.
Please type in the code:

Please do not post inappropriate pictures. Inappropriate pictures include pictures of minors and nudity.
The owner of this web site reserves the right to delete such material.

photo Add a picture: