データ構造とアルゴリズム
文字列の中からパターンを探すBM法(ボイヤー・ムーア法)の特徴として正しいものはどれか。
- Aパターンの末尾の文字から比べ、一致しなかったテキストの文字がパターンに含まれないなどの情報を使って、パターンを一度に大きくずらす
- Bテキストの先頭から1文字ずつずらしながら、毎回パターンの先頭から最後まですべての文字を比べる
- Cテキストとパターンの両方を整列してから二分探索で探す
答えと解説を見る
正解：A. パターンの末尾の文字から比べ、一致しなかったテキストの文字がパターンに含まれないなどの情報を使って、パターンを一度に大きくずらす
BM法は、パターンを末尾の文字から比べ、不一致になったテキストの文字がパターンに含まれなければ、パターン全体をその文字の先までずらせる、といった表を前もって作っておきます。そのため、自然な文章ではテキストの多くの文字を比べずに飛ばすことができます。テキストの長さを n、パターンの長さを m とすると、1文字ずつずらしてすべて比べる素朴な方法は最悪 O(nm) かかります。KMP法も不一致の情報を使ってずらしますが、こちらはパターンの先頭から比べ、最悪でも O(n + m) を保証します。
- A. 正しい。末尾から比べ、不一致の文字の情報で大きくずらすのがBM法です。
- B. 素朴な(力任せの)方法で、最悪 O(nm) かかります。
- C. 文字列の中の位置を探す問題なので、整列すると位置の情報が失われます。