ボイヤー・ムーア法(BM法、Boyer-Moore)文字列検索アルゴリズム ~Delphiでお手軽プログラミング
ボイヤー・ムーア法(BM法、Boyer-Moore)ユニット
文字列から部分文字列を探索するアルゴリズムで、部分文字列の末尾から探索するアルゴリズムだそうです。unit UBoyerMoore; interface uses System.SysUtils; //ボイヤー・ムーア法(BM法、Boyer-Moore)文字列探索アルゴリズム //Text文字列からPattern部分文字列を探索探して、0基準の見つかった位置の配列を返す function BMSearchText(Text,Pattern:string):TArray<Cardinal>; implementation function BMSearchText(Text,Pattern:string):TArray<Cardinal>; var TextLen, PatternLen, k, DiffPos, LeftOverLen, LeftOverPos:Integer; DiffChar, LeftOver:string; begin SetLength(result,0); TextLen:=Text.Length; PatternLen:=Pattern.Length; k:=PatternLen-1;//0から数えたtextの探索文字番目 while k<TextLen do begin DiffPos:=0; while DiffPos<PatternLen do begin if (Text.Substring(k-DiffPos,1)<>Pattern.Substring(PatternLen-1-DiffPos,1)) then begin break; end; inc(DiffPos); end; if DiffPos=PatternLen then //位置kでPattern文字列が一致した場合 begin SetLength(result,Length(result)+1); result[Length(result)-1]:=k-PatternLen+1; Inc(k,PatternLen); end else //位置kでPattern文字列が不一致の場合 begin //不一致文字 DiffChar:=Text.Substring(k-DiffPos,1); //パターン残り不一致文字列 LeftOver:=Pattern.Substring(0,PatternLen-DiffPos); LeftOverLen:=LeftOver.Length; //不一致文字がパターン残り文字列にあるか LeftOverPos:=1; while LeftOverPos<LeftOverLen do begin if LeftOver.SubString(LeftOverLen-1-LeftOverPos,1)=DiffChar then begin Break; end; Inc(LeftOverPos); end; Inc(k,LeftOverPos); end; end; end; end.
UBoyerMooreユニットを使う(例1)
unit Unit1;
interface
uses
Winapi.Windows, Winapi.Messages, System.SysUtils, System.Variants, System.Classes, Vcl.Graphics,
Vcl.Controls, Vcl.Forms, Vcl.Dialogs, Vcl.StdCtrls;
type
TForm1 = class(TForm)
Button1: TButton;
Memo1: TMemo;
procedure Button1Click(Sender: TObject);
private
{ Private 宣言 }
public
{ Public 宣言 }
end;
var
Form1: TForm1;
implementation
{$R *.dfm}
uses UBoyerMoore;
procedure TForm1.Button1Click(Sender: TObject);
var text,pattern:string;
p:TArray<Cardinal>;
i:integer;
begin
Memo1.Lines.Clear;
text:='あいうえお' +#13#10+
'あいうえおかきくけこ' +#13#10+
'あいうえおかきくけこさしすせそ' +#13#10+
'あいうえおかきくけこさしすせそたちつてと' +#13#10+
'あ';
pattern:='けこさ';
p:=BMSearchText(text,pattern);
if Length(p)=0 then
begin
Memo1.Lines.Add('「'+pattern+'」はありませんでした');
end
else
begin
for i := Low(p) to High(p) do
begin
memo1.Lines.Add(
IntToStr(p[i]) + ':'+
text.Substring(p[i],Length(pattern))
);
end;
end;
end;
end.
UBoyerMooreユニットを使う(例2)
unit Unit1;
interface
uses
Winapi.Windows, Winapi.Messages, System.SysUtils, System.Variants, System.Classes, Vcl.Graphics,
Vcl.Controls, Vcl.Forms, Vcl.Dialogs, Vcl.StdCtrls;
type
TForm1 = class(TForm)
Button1: TButton;
Memo1: TMemo;
procedure Button1Click(Sender: TObject);
private
{ Private 宣言 }
public
{ Public 宣言 }
end;
var
Form1: TForm1;
implementation
{$R *.dfm}
uses UBoyerMoore;
procedure TForm1.Button1Click(Sender: TObject);
var text,pattern:string;
p:TArray<Cardinal>;
i:integer;
begin
Memo1.Lines.Clear;
text:='あいうえお' +#13#10+
'あいうえおかきくけこ' +#13#10+
'あいうえおかきくけこさしすせそ' +#13#10+
'あいうえおかきくけこさしすせそたちつてと' +#13#10+
'あ';
pattern:=#13#10;
p:=BMSearchText(text,pattern);
if Length(p)=0 then
begin
Memo1.Lines.Add('「改行」はありませんでした');
end
else
begin
for i := Low(p) to High(p) do
begin
Memo1.Lines.Add(
IntToStr(p[i]) + ':改行文字の位置'
);
end;
end;
end;
end.