この記事での学習内容 基本情報 応用情報
文字列処理のアルゴリズムを理解する。
用語例：文字列照合、KMP法（クヌース・モリス・プラット法）、BM法（ボイヤ・ムーア法）
文字列処理のアルゴリズム
文字列処理のアルゴリズムは、一連の文字の並びを処理するアルゴリズムです。
- 連結： 一つの文字列の後へ別の文字列を追加して、一つの文字列にします。
- 挿入： 文字列の途中に別の文字列を挿入して、一つの文字列にします。
- 削除： 文字列の一部の文字を取り除いて、残りを一連の文字列にします。
- 照合： 文字列が別の文字列の中に含まれるか、有無を調べて位置を特定します。
順次探索法
- 対象の文字列の先頭の文字から、特定の文字列を一文字ずつ照合する。
すべての文字が一致したら、全体の処理を終了して対象の文字列の位置を返す。 - 対象の文字列の１文字後ろから１の処理を反復する。対象の文字列の最後を越えたら、探索失敗として終了する。
ボイヤ・ムーア法（BM法）
ボイヤとムーアによって考案された、高速の文字列照合アルゴリズムです。特定の文字列の後尾から前の方へ照合することと、一致しない場合には、複数の文字をスキップすることが特徴です。
- 特定の文字列を前処理して、「特定の文字が何文字目に出現するかを表す表」「一致した文字のパターンと、その場合にスキップしていい文字数を対応付ける表」の２表を作成する。
- 対象の文字列の先頭部分を特定の文字列の後尾から前方向へ、文字の比較をすすめる。
一致したら全体の処理を終了して、対象の文字列の位置を返す。 - 一致しなかったら、比較時に得られた情報と１で作った表を元にして、文字をスキップし、２の処理に戻る。