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