[Back to FINDREPL SWAG index]  [Back to Main SWAG index]  [Original]

  Hi, Andy:

  ...Here's a demo program of the Boyer-Moore search algorithm.

  The basic idea is to first create a Boyer-Moore index-table
  for the string you want to search for, and then call the
  BMsearch routine. *Remember* to turn-off "range-checking"
  {$R-} in your finished program, otherwise the BMSearch will
  take 3-4 times longer than it should.

              (* Public-domain demo of Boyer-Moore search algorithm.  *)
              (* Guy McLoughlin - May 1, 1993.                        *)
program DemoBMSearch;

              (* Boyer-Moore index-table data definition.             *)
type
  BMTable  = array[0..127] of byte;

  (***** Create a Boyer-Moore index-table to search with.             *)
  (*                                                                  *)
  procedure Create_BMTable({input }     Pattern : string;
                           {update} var     BMT : BMTable);
  var
    Index : byte;
  begin
    fillchar(BMT, sizeof(BMT), length(Pattern));
    for Index := 1 to length(Pattern) do
      BMT[ord(Pattern[Index])] := (length(Pattern) - Index)
  end;        (* Create_BMTable.                                      *)

  (***** Boyer-Moore Search function. Returns 0 if string is not      *)
  (*     found. Returns 65,535 if BufferSize is too large.            *)
  (*     ie: Greater than 65,520 bytes.                               *)
  (*                                                                  *)
  function BMsearch({input } var Buffer;
                                 BuffSize : word;
                             var BMT      : BMTable;
                                 Pattern  : string) : {output} word;
  var
    Buffer2 : array[1..65520] of char absolute Buffer;
    Index1,
    Index2,
    PatSize : word;
  begin
    if (BuffSize > 65520)  then
      begin
        BMsearch := $FFFF;
        exit
      end;
    PatSize := length(Pattern);
    Index1 := PatSize;
    Index2 := PatSize;
    repeat
      if (Buffer2[Index1] = Pattern[Index2]) then
        begin
          dec(Index1);
          dec(Index2)
        end
      else
        begin
          if (succ(PatSize - Index2) > (BMT[ord(Buffer2[Index1])])) then
            inc(Index1, succ(PatSize - Index2))
          else
            inc(Index1, BMT[ord(Buffer2[Index1])]);
          Index2 := PatSize
        end;
    until (Index2 < 1) or (Index1 > BuffSize);
    if (Index1 > BuffSize) then
      BMsearch := 0
    else
      BMsearch := succ(Index1)
  end;        (* BMsearch.                                            *)

type
  arby_64K = array[1..65520] of byte;

var
  Index   : word;
  st_Temp : string[10];
  Buffer  : ^arby_64K;
  BMT     : BMTable;

BEGIN
  new(Buffer);
  fillchar(Buffer^, sizeof(Buffer^), 0);
  st_Temp := 'Gumby';
  move(st_Temp[1], Buffer^[65516], length(st_Temp));
  Create_BMTable(st_Temp, BMT);
  Index := BMSearch(Buffer^, sizeof(Buffer^), BMT, st_Temp);
  writeln(st_Temp, ' found at offset ', Index)
END.
                               - Guy
---
 þ DeLuxeý/386 1.25 #5060 þ
 * Rose Media, Toronto, Canada : 416-733-2285
 * PostLink(tm) v1.04  ROSE (#1047) : RelayNet(tm)

                                                           

[Back to FINDREPL SWAG index]  [Back to Main SWAG index]  [Original]