home *** CD-ROM | disk | FTP | other *** search
/ POINT Software Programming / PPROG1.ISO / pascal / swag / findrepl.swg / 0001_BMFIND.PAS.pas next >
Encoding:
Pascal/Delphi Source File  |  1993-05-28  |  3.2 KB  |  99 lines
  1.  
  2.   Hi, Andy:
  3.  
  4.   ...Here's a demo program of the Boyer-Moore search algorithm.
  5.  
  6.   The basic idea is to first create a Boyer-Moore index-table
  7.   for the string you want to search for, and then call the
  8.   BMsearch routine. *Remember* to turn-off "range-checking"
  9.   {$R-} in your finished program, otherwise the BMSearch will
  10.   take 3-4 times longer than it should.
  11.  
  12.               (* Public-domain demo of Boyer-Moore search algorithm.  *)
  13.               (* Guy McLoughlin - May 1, 1993.                        *)
  14. program DemoBMSearch;
  15.  
  16.               (* Boyer-Moore index-table data definition.             *)
  17. type
  18.   BMTable  = array[0..127] of byte;
  19.  
  20.   (***** Create a Boyer-Moore index-table to search with.             *)
  21.   (*                                                                  *)
  22.   procedure Create_BMTable({input }     Pattern : string;
  23.                            {update} var     BMT : BMTable);
  24.   var
  25.     Index : byte;
  26.   begin
  27.     fillchar(BMT, sizeof(BMT), length(Pattern));
  28.     for Index := 1 to length(Pattern) do
  29.       BMT[ord(Pattern[Index])] := (length(Pattern) - Index)
  30.   end;        (* Create_BMTable.                                      *)
  31.  
  32.   (***** Boyer-Moore Search function. Returns 0 if string is not      *)
  33.   (*     found. Returns 65,535 if BufferSize is too large.            *)
  34.   (*     ie: Greater than 65,520 bytes.                               *)
  35.   (*                                                                  *)
  36.   function BMsearch({input } var Buffer;
  37.                                  BuffSize : word;
  38.                              var BMT      : BMTable;
  39.                                  Pattern  : string) : {output} word;
  40.   var
  41.     Buffer2 : array[1..65520] of char absolute Buffer;
  42.     Index1,
  43.     Index2,
  44.     PatSize : word;
  45.   begin
  46.     if (BuffSize > 65520)  then
  47.       begin
  48.         BMsearch := $FFFF;
  49.         exit
  50.       end;
  51.     PatSize := length(Pattern);
  52.     Index1 := PatSize;
  53.     Index2 := PatSize;
  54.     repeat
  55.       if (Buffer2[Index1] = Pattern[Index2]) then
  56.         begin
  57.           dec(Index1);
  58.           dec(Index2)
  59.         end
  60.       else
  61.         begin
  62.           if (succ(PatSize - Index2) > (BMT[ord(Buffer2[Index1])])) then
  63.             inc(Index1, succ(PatSize - Index2))
  64.           else
  65.             inc(Index1, BMT[ord(Buffer2[Index1])]);
  66.           Index2 := PatSize
  67.         end;
  68.     until (Index2 < 1) or (Index1 > BuffSize);
  69.     if (Index1 > BuffSize) then
  70.       BMsearch := 0
  71.     else
  72.       BMsearch := succ(Index1)
  73.   end;        (* BMsearch.                                            *)
  74.  
  75. type
  76.   arby_64K = array[1..65520] of byte;
  77.  
  78. var
  79.   Index   : word;
  80.   st_Temp : string[10];
  81.   Buffer  : ^arby_64K;
  82.   BMT     : BMTable;
  83.  
  84. BEGIN
  85.   new(Buffer);
  86.   fillchar(Buffer^, sizeof(Buffer^), 0);
  87.   st_Temp := 'Gumby';
  88.   move(st_Temp[1], Buffer^[65516], length(st_Temp));
  89.   Create_BMTable(st_Temp, BMT);
  90.   Index := BMSearch(Buffer^, sizeof(Buffer^), BMT, st_Temp);
  91.   writeln(st_Temp, ' found at offset ', Index)
  92. END.
  93.                                - Guy
  94. ---
  95.  ■ DeLuxe²/386 1.25 #5060 ■
  96.  * Rose Media, Toronto, Canada : 416-733-2285
  97.  * PostLink(tm) v1.04  ROSE (#1047) : RelayNet(tm)
  98.  
  99.