アルゴリズムとプログラミング
Boyer-Moore法（BM法）による文字列検索の特徴として正しいものはどれか。
ア.事前にテキスト全体をインデックス化してから検索するため、前処理に時間がかかる。
イ.パターンを左から右へ順番に比較し、不一致時は1文字ずつ右へシフトする。
ウ.不一致が発生した際にパターンの末尾側から照合し、大幅にスキップできるため平均的に高速である。正解
エ.常にO(n)の最悪計算量を保証する文字列検索アルゴリズムである。
解説
BM法は「末尾から比較して不一致なら大ジャンプ」する賢いアルゴリズム。なるべく比較回数を減らして電話帳から名前を探す忍耐勝ちな方式です。
なぜ ウ が正解か
Boyer-Moore法の核心は「パターンの右端から照合を始め、不一致が起きたときにテキスト内の文字がパターンのどこかにあるかを事前テーブルで調べ、大きくスキップする」ことです。「好字則（Good Suffix Rule）」と「悪字則（Bad Character Rule）」の2つのシフト量テーブルを使い、最悪O(nm)ですが実用上は非常に高速です。
出典: AI生成問題（学習用）