Kein Wunder das die BM-Suche so langsam: Hier wird ja jedesmal der String gekürzt und BM liefert eh falsche Ergebnisse, denn er bricht beim ersten Fund nicht ab sondern sucht weiter. Da scheint ein 'exit' zu fehlen:
Delphi-Quellcode:
...
if j=m then
begin
// Muster gefunden
result := k - j + 1;
exit; // <<<<<<<<<<<<<<<<<<<<<<< Fehlt
// Die nächste Zeile ist auskommentiert, denn wir wollen ja nicht weitersuchen
// k := k + m; //oder: k+1, oder: break; je nachdem, wie man den Text komplett durchsucht haben will
end else
...
Der Code lässt sich im Übrigen leicht modifizieren, um ein sehr schnelles PosEx_BMH zu implementieren, d.h. 'Suche ab Position'. Hier die Korrekturen.
Delphi-Quellcode:
function Search_BMH_Unrolled(sourcestring,suchstr: String;Offset : integer=1): Integer;
var
m, n, k, j: Integer;
BC : TBC_IntArray;
BC_last : Integer;
Large : Integer;
begin
m := Length(suchstr);
n := Length(sourcestring)-Offset+1;
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 := Offset-1;
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;
exit;
// 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;
PS: Kann mal einer 'Horsepool' richtig schreiben? Das ist kein Pool für Pferde, sondern der Mann heißt 'Nigel Horspool'.