力任せ法、KMP法のどちらのアルゴリズムも、検索ワードの先頭から比較をしていました。逆に、末尾から比較をすることで効率を上げるのがBM法です。BM法も考案した人の名前(Boyer-Moore)の頭文字です。末尾の文字が不一致であれば、検索ワード全体としても不一致になります。そこで、次のマッチングでは検索ワードの文字数分全部ずらしてしまってもよさそうです。このように一気にジャンプできるので効率がよさそうです。不一致になったとき、文字列側の文字が検索ワードに含まれる文字だった場合、全部ずらしてはいけません。途中でマッチする可能性があります。従って、不一致になったときの文字の種類ごとに、検索ワードを何文字シフトするかをあらかじめ計算しておきます。シフト文字数は次のようになります。下図に示した例では、'a'=2、'b'=1、それ以外は5になります。シフトした後、文字列のポインタがあった場所の文字と検索ワードの文字が一致することに注目してください。先ほどのプログラムの49行目、「末尾2」というコメントがある行の下に以下のプログラムを追加してください。-->プログラムを解説します。文字ごとのシフト文字数を計算する関数です。BMSkipはオブジェクト的に使うようになっています。引数strには検索ワードが入ります。3行目シフト文字数を格納する配列を定義しています。検索ワードのそれぞれの文字について、後ろから何文字目かを計算して入れています。検索ワードの文字に重複がある場合、後から計算したもので上書きされます。後ろの方の文字が優先されます。実際の探索を行っているときにシフト文字数を取得する関数です。skip_offsetに値が設定されていればその文字数を返し、なければ検索ワードの文字数を返します。15〜29行目BM法の文字列探索を行う関数です。16行目シフト文字数を計算します。変数posは文字列側のポインタです。文字列と検索ワードを後ろから比較していきます。全部一致したらjが-1になるので一致した文字の位置を返します。デバッガで様子を見る場合は、18行目のfor文にブレークポイントを置くとよいでしょう。posの値が1ずつでなく、多数増えながら検索している様子が分かると思います。メールマガジンをご購読ください。申し込みページへITmediaはアイティメディア株式会社の登録商標です。