Articles   Members Online:
-Article/Tip Search
-News Group Search over 21 Million news group articles.
-Delphi/Pascal
-CBuilder/C++
-C#Builder/C#
-JBuilder/Java
-Kylix
Member Area
-Home
-Account Center
-Top 10 NEW!!
-Submit Article/Tip
-Forums Upgraded!!
-My Articles
-Edit Information
-Login/Logout
-Become a Member
-Why sign up!
-Newsletter
-Chat Online!
-Indexes NEW!!
Employment
-Build your resume
-Find a job
-Post a job
-Resume Search
Contacts
-Contacts
-Feedbacks
-Link to us
-Privacy/Disclaimer
Embarcadero
Visit Embarcadero
Embarcadero Community
JEDI
Links
Karp-Rabin string searching Turn on/off line numbers in source code. Switch to Orginial background IDE or DSP color Comment or reply to this aritlce/tip for discussion. Bookmark this article to my favorite article(s). Print this article
15-Sep-02
Category
Object Pascal-Strings
Language
Delphi All Versions
Views
37
User Rating
No Votes
# Votes
0
Replies
0
Publisher:
DSP, Administrator
Reference URL:
DKB
			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;


			
Vote: How useful do you find this Article/Tip?
Bad Excellent
1 2 3 4 5 6 7 8 9 10

 

Advertisement
Share this page
Advertisement
Download from Google

Copyright © Mendozi Enterprises LLC