Schnellster Stringmatching-Algorithmus in ASM übersetzen

[Gausi]

Ich habe den Horspool "ausgerollt". Kann man auch bei Boyer-Moore selbst anwenden, dadurch wird BM in eingen Fällen doppelt so schnell. Der Trick ist, einge Dinge auszulagern. Dafür ändert man das Bad-Character-Array für das letzte Zeichen des Musters ab und kann so in einer "schnellen Schleife" das Muster rüberschieben, bis mal ein passendes Zeichen gefunden wurde. dann geht man aus der schnellen Schleife raus und fängt mit der Überprüfung an.
Dieser Trick funktioniert bei Quicksearch allerdings nicht .

Delphi-Quellcode:

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(t,p: String): Integer;
var m, n, k, j: Integer;
    BC: TBC_IntArray;
    BC_last: Integer;
    Large: Integer;
begin
  m := Length(p);
  n := Length(t);
  Large := m + n + 1;

  BC := PreProcess_BMH_BC(p);

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

  k := m;
  result := 0;

  while k <= n do
  begin
      //fast loop
      repeat
        k := k + BC[t[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 (p[m-j] = t[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 t[k] = p[m] then
            k := k + BC_last    // Hier dann den original-Wert nehmen
          else
            k := k + BC[t[k]];
      end;
  end;
end;