BM法についての記事を書いたとたんに、 「最速の文字列検索アルゴリズムってなんだ?」 と思って調べまくった次第です(;^ω^)。この無駄な凝り性はプラスにもマイナスにも働きそうで怖い。 そしたらBM法の亜種がいくつか研究されてるみたいですね。 んで、この亜種についての一般的な話を。 (あ、BM法の記事:http://d.hatena.ne.jp/g940425/20100522/1274520718 を見てない人はわかりにくいかもです(;´・ω・`)) Boyer-Mooreのアルゴリズムの要は、「テキストのどの文字で不一致が起こったか」によって一気に先へ先へとジャンプしていくところだったわけだ。 上のテキストから下のパターンを検索するとき、 BM法では、パターンの後ろから見ていって、 初めて不一致となったこの位置に パターン中の同じ文字を合わせることでパターンの位置を何文字か(例では二文
![HorspoolのアルゴリズムとSunday's Quick Search - 似非学問的な手記](https://cdn-ak-scissors.b.st-hatena.com/image/square/ef8a5692fbcdb7c24b98571e23c297bb5d36f05b/height=288;version=1;width=512/https%3A%2F%2Fcdn-ak.f.st-hatena.com%2Fimages%2Ffotolife%2Fg%2Fg940425%2F20100524%2F20100524181704.png)