BMサーチというアルゴリズム

質問

昔、CマガジンでBMサーチという文字列を早く検索するアルゴリズムがあったのですが、その本がなく、詳しいソースや解説をしているサイトや本を探しています。

moto = ".....";

if ( strcmp(moto, "AA") == 0 ) {

}else if ( strcmp(moto, "AB") == 0 ) {
...
}

と、BMサーチではどちらが早いのでしょうか？
Cライブラリになっているので、中でBMサーチみたいなことはしているのでしょうか？

回答No.2

nas02 · ベストアンサー

Googleで検索すると以下のようなサイトに解説がありました。

ボイヤー-ムーア文字列検索アルゴリズム
http://ja.wikipedia.org/wiki/%E3%83%9C%E3%82%A4%E3%83%A4%E3%83%BC-%E3%83%A0%E3%83%BC%E3%82%A2%E6%96%87%E5%AD%97%E5%88%97%E6%A4%9C%E7%B4%A2%E3%82%A2%E3%83%AB%E3%82%B4%E3%83%AA%E3%82%BA%E3%83%A0

９．Boyer-Mooreの検索法
http://itpro.nikkeibp.co.jp/article/COLUMN/20061024/251654/?ST=develop&P=9

検索アルゴリズム
http://www2.starcat.ne.jp/~fussy/algo/algo7-4.htm

中々ユニークな検索法ですね。
多分、標準のCライブラリはこのような事はしていないと思います。

回答No.3

επιστημη（@episteme）

BM法は検索文字列が長くないとさほどに速くありません。
Cライブラリでの文字列検索はその多くが:
検索文字列の最初の1文字を探し、そこから続く文字列が検索文字列と一致するかを調べています。

いまどきのメモリもCPUも高速なのでよほど効率の悪いアルゴリズムでない限りさほどの差はありませんけどね。

回答No.1

asuncion

「BM法」で検索すると、多くのサイトがヒットします。
また、アルゴリズムに関する本を探して、
文字列探索に関する章があれば、
BM法について書いてあるかもしれません。書いてないかもしれません。