大人気のKMP法&BM法

この日記へのアクセス元を見てみると「KMP法 BM法」でウェブ検索してここにたどり着いた人が何人かいるみたい。しかもここ数日だけ。なんでこうなるか。わかってます。筧先生の課題がわからなくてウェブで調べてる人々だ! 提出が昨日までだったし。
この課題、BM法という文字列検索アルゴリズムを自力で完成させて性能まで調べろと言うもの。しかしこのBM法は前に書いたようにややこしい。そして言ってしまうと、ウェブ検索ではまともな答えは見つかりません。
BM法を昨日ずっと考えていたけど結局わからなくて、今日になってやっと完成できました。一日遅れだね。おかげで、今日提出するコンパイラ拡張という課題が終わらなかったわけですが。
ここで、BM法とは何か。文字列からあるパターンを探索するとき、パターンを後ろから比較することで比較回数を減らそうってアルゴリズムです。

abcabcabcd
abcd
   ↑       比較、違う。aに初めて出会うのはパターンの右から3つ目のはず
   abcd    そこで、3つずらす
      ↑    やはり違う。
      abcd
      ↑↑↑↑ ここで一致

10文字の文字列の中から、たった6回の比較で検索ができました。ここでは、文章側の文字すべての種類に、「この文字で不一致だったら何文字ジャンプできる」という情報をパターンから生成しておくのです。ただ、これだけではまだ不十分。パターンと文章の組み合わせによっては・・・

bbbbbbabbb
abbb
↑↑↑↑     先頭の文字で不一致
 abbb    bはパターンの左端にある文字なので、さっきのようなジャンプは使えない
 ↑↑↑↑
  abbb
  ↑↑↑↑   何回同じところを比較する気だ、と(^^;)

この問題をどうするか、が今回の課題。
そこで、パターンの各文字に、ここで不一致起こしたら何個ジャンプできるか、も別に設定しておいてジャンプの効率を良くするのです。

abbb
4111

aで不一致起こしたなら、その右側3つにaはないことがわかっているのだから、4つずらしていいはず、とわかりますね。しかし右から3つ目のbで不一致を起こしたならbbの並びはすぐ右にもあるので2つ以上ずらすと危険。そういうのをパターンの文字ごとに算出しておくのです。あとは、2種類のジャンプ法のうち大きい方に従ってジャンプしていけばいいということになります。

今日完成できなかった課題も、24時を過ぎたところで何とか完成。ちっ遅かった。C言語のサブセットみたいな言語(WL)を改良しろって言う課題なんだけど、このWL、C言語系のくせにポインタがない。よってポインタ変数を搭載してやろうと躍起になっていたのです。かなり手間食って、正直後悔してる(^^;)