「ボイヤー-ムーア文字列検索アルゴリズム」の版間の差分

この[[アルゴリズム]]では検索[[文字列]]（パターン）の前処理を行い、検索対象テキストの前処理は行わない。したがって、テキストについて何度も検索を行わない場合に適している（他のアルゴリズムではテキスト側に前処理を施し、繰り返し[[検索]]を行うことで前処理のコストを償却する）。テキスト上の全文字をチェックする必要はなく、前処理で得た情報を活用してスキップしながら処理していく。一般にパターン文字列が長いほど検索が高速化される。検索文字列とテキストの間での不一致が発生するたびに、不一致であったという情報を最大限に利用して照合しなくてもいい位置を可能な限り排除することで、効率を向上させている。

 

<div class="thumb tright" style="width:160px;">

<div>

 

「{{mvar|P}} が {{mvar|T}} に'''一致'''する」とは {{mvar|P}} と文字列として[[同値類|等価]]な部分文字列 {{math|''T''[''i''..''j'']}} が存在することをいう。より具体的に、{{mvar|P}} が位置 {{mvar|k}} で {{mvar|T}} と一致するとは、{{mvar|k}} 番目から前方 {{math|len(''P'')}} 文字分を取り出した部分文字列 {{math|''T''[(''k'' &minus; len(''P'') + 1)..''k'']}} が {{mvar|P}} と文字列として等価であることをいう。

 

== アルゴリズム ==