Freepascal과 Lazarus를 위한 자작 Boyer-Moore-Horspool 문자열 검색 알고리 즘

아래의 코드는 Boyer-Moore-Horspool 문자열 검색 알고리즘을 직접 Freepascal / Lazarus로 구현한 코드입니다. Freepascal / Lazarus에서만 테스트되었습니다만, 델파이에서도 충분히 사용 가능하리라고 생각됩니다.

이 코드의 라이선스는 Lazarus가 채용한, 수정된 LGPL(LGPL+static link 허용)을 따릅니다. 사용하시는데 큰 문제는 없을겁니다.

간단한 사용법은 다음과 같습니다.

1. TPosBMH 객체를 생성합니다
2. TPosBMH.PosBMH()를 호출하면 첫번째 위치를 찾습니다
3. TPosBMH.PosBMHNext()를 호출하면 다음 위치를 찾습니다
4. 만일 찾는 대상이 더이상 없다면, TPosBMH는 Nil을 반환합니다

실제 코드는 다음과 같습니다. 도움이 되셨으면 좋겠습니다.

{
Unit PosBMH: Implementation of Boyer-Moor-Horpspool string search algorithm, optimized for consecutive searches

Create a TPosBMH object, use PosBMH() for initializing search, and PosBMHNext() for consecutive search. The return value is always PChar.

Can be used freely under the same license of LCL(Lazarus Component Library), which adopts modified LGPL.
(LGPL + allowing exception for static linking)

©Copyright 2012~2013 Robert Teminian(Hyunse Oh)
}
unit PosBMH;

{$mode objfpc}{$H+}

interface

uses
Classes, SysUtils;

type
TPosBMH = class(TObject)
private
FBMHLast: PChar;
FSubString: String;
FSubStringLength: SizeInt;
FBMHSkipTable: Array[0..255] of SizeInt;
procedure FBuildSkipTable();
procedure FPosBMH();
protected
BMHCursor: PChar;
public
function PosBMH(Needle: String; StartAt: PChar; EndAt: PChar): PChar;
function PosBMH(Needle: String; var Haystack: String): PChar;
function PosBMHNext: PChar;
end;

implementation

procedure TPosBMH.FBuildSkipTable();
var
i: Integer;
begin
for i:=0 to 255 do FBMHSkipTable[i]:=FSubStringLength;
for i:=1 to FSubStringLength do FBMHSkipTable[Byte(FSubString[i])]:=FSubStringLength-i;
end;

procedure TPosBMH.FPosBMH();
begin
while BMHCursor if FBMHSkipTable[Byte(BMHCursor^)]=0 then begin
Dec(BMHCursor, FSubStringLength-1);
if CompareByte(BMHCursor^, FSubString[1], FSubStringLength)=0 then Exit
else Inc(BMHCursor, FSubStringLength);
end else Inc(BMHCursor, FBMHSkipTable[Byte(BMHCursor^)]);
end;
BMHCursor:=nil;
end;

function TPosBMH.PosBMH(Needle: String; StartAt: PChar; EndAt: PChar): PChar;
begin
FSubString:=Needle;
FSubStringLength:=Length(FSubString);
BMHCursor:=StartAt;
FBMHLast:=EndAt;
FBuildSkipTable();
FPosBMH();
Result:=BMHCursor;
end;

function TPosBMH.PosBMH(Needle: String; var Haystack: String): PChar;
begin
Result:=PosBMH(Needle, @Haystack[1], @Haystack[Length(Haystack)]);
end;

function TPosBMH.PosBMHNext: PChar;
begin
if(BMHCursorNil) then begin
Inc(BMHCursor, FSubStringLength);
FPosBMH();
end;
Result:=BMHCursor;
end;

end.