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;