この記事での学習内容 基本情報 応用情報

文字列処理のアルゴリズムを理解する。

用語例：文字列照合、KMP法（クヌース・モリス・プラット法）、BM法（ボイヤ・ムーア法）

文字列処理のアルゴリズム

文字列処理のアルゴリズムは、一連の文字の並びを処理するアルゴリズムです。

• 連結：　一つの文字列の後へ別の文字列を追加して、一つの文字列にします。
• 挿入：　文字列の途中に別の文字列を挿入して、一つの文字列にします。
• 削除：　文字列の一部の文字を取り除いて、残りを一連の文字列にします。
• 照合：　文字列が別の文字列の中に含まれるか、有無を調べて位置を特定します。

順次探索法

1. 対象の文字列の先頭の文字から、特定の文字列を一文字ずつ照合する。
   すべての文字が一致したら、全体の処理を終了して対象の文字列の位置を返す。
2. 対象の文字列の１文字後ろから１の処理を反復する。対象の文字列の最後を越えたら、探索失敗として終了する。

ボイヤ・ムーア法（BM法）

ボイヤとムーアによって考案された、高速の文字列照合アルゴリズムです。特定の文字列の後尾から前の方へ照合することと、一致しない場合には、複数の文字をスキップすることが特徴です。

1. 特定の文字列を前処理して、「特定の文字が何文字目に出現するかを表す表」「一致した文字のパターンと、その場合にスキップしていい文字数を対応付ける表」の２表を作成する。
2. 対象の文字列の先頭部分を特定の文字列の後尾から前方向へ、文字の比較をすすめる。
   一致したら全体の処理を終了して、対象の文字列の位置を返す。
3. 一致しなかったら、比較時に得られた情報と１で作った表を元にして、文字をスキップし、２の処理に戻る。