unit BoyerMoore;
interface
uses
SysUtils;
type
TDirection = (dForward = 1, dBackward = -1);
TBoyerMoore =
class
private
FLastSearchStr :
String;
FLastSearchDir : TDirection;
FBadTable, FGoodTable :
array of Integer;
public
constructor Create;
function PosBM(
const Pattern, Text:
String; Offset : Integer = 1;
const Dir : TDirection = dForward): Integer;
register;
end;
implementation
{ TBoyerMoore }
constructor TBoyerMoore.Create;
begin
// Array für Unicode initialisieren
SetLength(FBadTable, 65536);
end;
// *************
// P o s B M
// *************
//
// Boyer-Moore Stringsuche
//
// Eingabe:
// --------
// Pattern: Suchmuster
// Text: Suchtext
// Offset: Position ab der gesucht werden soll
// Dir: Richtung in die gesucht werden soll: dForward = vorwärts dBackward = rückwärts
//
// Rückgabe:
// ---------
// =0: kein Match
// >0: Position des ersten Match
//
function TBoyerMoore.PosBM(
const Pattern, Text:
String; Offset: Integer;
const Dir: TDirection): Integer;
register;
var
i, j, k, iDir, iPLen, iTLen, iOffKorr, iBadSkip : Integer;
label
NextTryFwd, MatchedFwd, NextTryBwd, MatchedBwd, NextStep;
begin
Result := 0;
iPLen := Length(Pattern);
iTLen := Length(Text);
iDir := Ord(Dir);
if (iPLen > iTLen)
or (Offset = 0)
or (Offset > iTLen)
then
raise Exception.Create('
PosBMEx: Invalid parameter!');
// Good- und Bad-Table nur neu erzeugen, wenn neues Suchmuster verwendet wird
// oder die Suchrichtung wechselt.
if (FLastSearchStr <> Pattern)
or (FLastSearchDir <> Dir)
then
begin
// Bad-Table wieder auf 0 setzen
for i := 1
to Length(FLastSearchStr)
do
FBadTable[Ord(FLastSearchStr[i])] := 0;
// Good-Table anlegen
SetLength(FGoodTable, iPLen + 1);
// Sprungtabellen abhängig von der Richtung erzeugen
if Dir = dForward
then
begin
// Bad-Character-Table vorwärts
for i := 1
to iPLen
do
FBadTable[Ord(Pattern[i])] := - i;
// iPLen später addieren
// Good-Suffix-Table vorwärts
for j := 0
to iPLen
do
begin
for i := iPLen-1
downto 1
do
begin
for k := 1
to j
do
begin
if i - k < 0
then
Goto MatchedFwd;
if (Pattern[iPLen - k + 1] <> Pattern[i - k + 1])
then
Goto NextTryFwd;
end;
Goto MatchedFwd;
NextTryFwd:
end;
MatchedFwd:
FGoodTable[j] := iPLen - i;
end;
end
else
begin
// Bad-Character-Table rückwärts
for i := iPLen
downto 1
do
FBadTable[Ord(Pattern[i])] := i - 1 - iPLen;
// iPLen später wieder addieren
// Good-Suffix-Table rückwärts
for j := 0
to iPLen
do
begin
for i := 2
to iPLen
do
begin
for k := 1
to j
do
begin
if i + k - 1 > iPLen
then
Goto MatchedBwd;
if (Pattern[k] <> Pattern[i + k - 1])
then
Goto NextTryBwd;
end;
Goto MatchedBwd;
NextTryBwd:
end;
MatchedBwd:
FGoodTable[j] := i - 1;
end;
end;
FLastSearchStr := Pattern;
FLastSearchDir := Dir;
end;
Offset := Offset + (iPLen - 1) * iDir;
// Startoffset
case Dir
of
dForward:
iOffKorr := iPLen;
dBackward:
iOffKorr := 1;
end;
while (Offset <= iTLen)
and (OffSet >= 0)
do
begin
j := 0;
// Anzahl der Übereinstimmungen
while j < iPLen
do
begin
if Text[Offset - j * iDir] = Pattern[iOffKorr - j * iDir]
then
inc(j)
else
begin
iBadSkip := FBadTable[Ord(Text[Offset - j * iDir])] + iPLen - j;
if iBadSkip > FGoodTable[j]
then
begin
inc(Offset, iBadSkip * iDir);
// Bad-Table verwenden
end
else
begin
inc(Offset, FGoodTable[j] * iDir);
// Good-Table verwenden
end;
Goto NextStep;
end;
end;
Exit(Offset - iOffKorr + 1);
NextStep:
end;
end;
end.