Boyer Moore Algorithmus

[p80286]

Hast Du denn das Delphi-Original nicht?

Delphi-Quellcode:

unit BoyerMooreHorsepool;

interface

function Search_BMH_Unrolled(sourcestring,suchstr: String): Integer;

implementation


type
  TBC_IntArray = Array[Char] of Integer;


function PreProcess_BMH_BC(p: String): TBC_IntArray;
var
  i,
  m : Integer;
  c : Char;
begin
  m := Length(p);
  for c := low(Char) to High(Char) do
    result[c] := m;
  for i := 1 to m-1 do
    result[p[i]] := m-i;
end;

// Suche mit Horspool, direkt die unrolled-Variante. Sehr ähnlich zu BM_Unrolled
function Search_BMH_Unrolled(sourcestring,suchstr: String): Integer;
var
  m, n, k, j: Integer;
  BC      : TBC_IntArray;
  BC_last : Integer;
  Large   : Integer;
begin
  m := Length(suchstr);
  n := Length(sourcestring);
  Large := m + n + 1;

  BC := PreProcess_BMH_BC(suchstr);

  // "echten" BC-Shift merken
  BC_last := BC[suchstr[m]];
  // BC(lastCh) mit "Large" überschreiben
  BC[suchstr[m]] := Large;

  k := m;
  result := 0;

  while k <= n do
  begin
      //fast loop
      repeat
        k := k + BC[sourcestring[k]];
      until k > n;

      //undo
      if k <= Large then
        //Muster nicht gefunden
        break
      else
        k := k - Large;

      j := 1;
      // slow loop
      while (j < m) and (suchstr[m-j] = sourcestring[k-j]) do
        inc(j);

      if j=m then
      begin
        // Muster gefunden
        result := k - j + 1;
        k := k + m; //oder: k+1, oder: break; je nachdem, wie man den Text komplett durchsucht haben will
      end else
      begin
          // Muster verschieben
          if sourcestring[k] = suchstr[m] then
            k := k + BC_last    // Hier dann den original-Wert nehmen
          else
            k := k + BC[sourcestring[k]];
      end;
  end;
end;

end.