ボイヤー・ムーア法(BM法、Boyer-Moore)文字列検索アルゴリズム ～Delphiでお手軽プログラミング

• ホーム
• Delphiでお手軽プログラミング
• ボイヤー・ムーア法(BM法、Boyer-Moore)文字列検索アルゴリズム ～Delphiでお手軽プログラミング

ボイヤー・ムーア法(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ユニットを使う（例１）

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ユニットを使う（例２）

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.