KMP法・BM法の対象試験と出題頻度
「クヌース・モリス・プラット法」「ボイヤー・ムーア法」というカタカナの名前を見て、手が止まった人も多いのではないでしょうか。
どちらも文字列探索(文字列照合)のアルゴリズムで、主戦場は応用情報技術者試験(AP)の午後問題です。午前の単独知識問題として問われることは稀で、頻出度はD。
ただし出るときは1問まるごと使われる「出たら重い」タイプなので、比較方向の違いだけは先に押さえておきたいところ。
出題情報を確認する
応用情報技術者(AP) 基本情報技術者(FE)
★★☆☆☆
頻出度D:午前では稀。ただし午後・科目Bで1問まるごと出題されることがある
KMP法・BM法の定義
文字列探索という上位概念を先に置くと、2つの手法の位置づけがはっきりします。テキスト(探される側の長い文字列)の中で、パターン(探す側の短い文字列)が最初に一致する位置を求める処理が文字列照合です。
KMP法はKnuth、Morris、Prattの3名、BM法はBoyerとMooreが、いずれも1977年に発表した手法。名称はすべて考案者の姓の並びで、意味を表す言葉は入っていません。
KMP法・BM法とは、
「テキスト中のパターンを、無駄な比較を省いて高速に探す文字列照合法」
です。
英和辞典で単語を引く場面を思い浮かべてみてください。
KMP法は「先頭から1文字ずつ照合し、いま一致していた部分の情報を使って後戻りをやめる」方式。
BM法は「末尾から比べて、パターンに無い文字を見た瞬間に大きくページを飛ばす」方式であり、飛ばし方の発想が正反対になっています。
📊 KMP法・BM法の基本情報
| 項目 | 内容 |
|---|---|
| 英語名 | KMP:Knuth-Morris-Pratt algorithm/BM:Boyer-Moore algorithm |
| 目的 | テキスト中でパターンが最初に一致する位置を求める |
| 比較方向 | KMP法=パターンの先頭から/BM法=パターンの末尾から |
| ずらし幅の根拠 | KMP法=パターン自身の繰り返し構造/BM法=不一致となったテキスト側の文字 |
| 身近な実装例 | grep、ripgrep、エディタの文字列検索(BM系の派生が主流) |
力まかせ法から見るKMP法・BM法の仕組み
まず基準となる「力まかせ法」とその弱点
力まかせ法(ナイーブ法)は、パターンの先頭から1文字ずつ比較し、不一致が出たら比較位置を1文字だけ進める素朴な方法。
線形探索法(リニアサーチ)の考え方を、単一の値ではなく文字の並びに当てはめたものと捉えれば十分でしょう。
弱点は、途中まで一致していた情報を毎回捨てて振り出しに戻る点にあります。
KMP法:ずらし幅はパターン自身の繰り返しから決まる
KMP法は不一致が起きた時点で「どこまで一致していたか」を手掛かりにし、ずらし幅をパターン自身の繰り返し構造から決めます。
電話番号を照合するとき、市外局番が一致済みだと分かっていればそこを読み直さない、という発想に近い。
テキスト側を後戻りして読み直す動きが消えるため、最悪でもO(n+m)で走り切る安定型です。
BM法:後ろから比べて「その文字は無い」を武器にする
BM法はパターンの末尾から先頭方向へ比較し、不一致となったテキスト側の文字がパターン内のどこに現れるかでずらし幅を決めます。
辞書を後ろから引くようなもので、「その文字はパターンに一つも無い」と判明した瞬間、パターンの長さ分をまとめて飛ばせる。この“無い”という情報が強く、平均的な速さでは他の2手法を上回ります。
実務でKMPやBMを自作する場面はほぼなく、筆者も使う側に回っています。
障害調査で数GBのログをgrepやripgrepにかけると一瞬で終わる一方、検索語を1〜2文字に縮めると急に遅くなる。
飛ばせる幅がパターンの長さで決まるBM系の性質が、体感としてそのまま表れる場面でした。
📊 3手法の比較方向とずらし幅
テキスト=ACBBMACABABC/パターン=ACAB
テキスト(12文字)
力まかせ法先頭から比較/3文字目で不一致 → ずらし幅 1
KMP法先頭から比較/一致済み「AC」の構造から → ずらし幅 2
BM法末尾(濃い枠)から比較/判定文字Bのスキップ数は4 → ずらし幅 4
同じ位置から始めても、不一致1回で稼げる距離が手法ごとに違う
3手法の計算量比較
値を並べると、BM法の「平均は速いが最悪は改善しない」という性格が見えてきます。
オーダー記法そのものの読み方はオーダー記法(計算量)で確認してください。
📊 力まかせ法・KMP法・BM法の比較(n=テキスト長/m=パターン長)
| 手法 | 比較方向 | 前処理 | 最悪計算量 | 実用上の速さ | 出題形態 |
|---|---|---|---|---|---|
| 力まかせ法 | 先頭から | なし | O(nm) | 短い文字列なら十分 | 二重ループの回数カウント |
| KMP法 | 先頭から | 繰り返し構造の解析 O(m) | O(n+m) | 最悪でも安定 | 定義・比較方向の知識 |
| BM法 | 末尾から | スキップ表の作成 O(m+文字種) | O(nm) | 平均で最速 | スキップ表作成とトレース |
📝 ポイント整理
・比較方向は、力まかせ法とKMP法が先頭から、BM法だけ末尾から
・ずらし幅の根拠は、KMP法がパターン自身の繰り返し、BM法が不一致文字
・最悪計算量が線形になるのはKMP法のみ。BM法は平均が速いだけ
・実務では自作より前に「検索対象を絞る」「索引を張る」方が効く
試験ではこう出る!文字列探索の出題パターン
出題は3つの型に整理できます。設問はスキップ表の作成と手トレースに集中しており、用語の暗記だけでは点になりません。
📝 IPA試験での出題パターン
パターン1:擬似コード穴埋め型
ずらし幅の式を添字で書かせる型。AP平成21年秋の「P.length-j」、FE平成27年秋の「PatLen-I」が該当し、引き算の向きと±1のずれを突いてくる。
パターン2:回数カウント型
比較や分岐の実行回数を問う型。AP平成21年秋 設問3(α=12回・β=8回)、FE平成27年秋 設問2(3回・7回・返却値9)、FE令和7年度 科目B問4(真となる回数8回)。
パターン3:表の作成型
スキップ数を直接埋めさせる型。AP平成21年秋 設問2のHIPOPOTAMUSがまさにこれ。
手を動かす以外の解法がない型が中心なので、スキップ表の作成手順を体に入れておくのが最短ルートになります。
ひっかけは比較方向と根拠の入れ替えに集中しています。次の4つで守り切れます。
⚠️ ひっかけ早見表
| 誤答の値・選択肢 | その正体 |
|---|---|
| BM法はパターンの先頭から比較 | KMP法との比較方向の逆転 |
| KMP法のずらし幅は不一致文字で決まる | BM法の根拠との入れ替え |
| 同じ文字は末尾から遠い方の距離を採用 | 上書き順序の誤り。−1を返す不具合の原因 |
| BM法は最悪計算量も必ず有利 | 最悪はO(nm)級で力まかせ法と同等 |
📝 試験区分別の対策方針
・AP:午後選択問題。擬似コードのトレースとスキップ表作成を手書きで練習
・FE:科目Bは力まかせ法の二重ループ。KMP/BMは定義と比較方向を暗記
・IP・SG:出題範囲外。深追い不要
過去問の出題実績とBM法のトレース表を見る
AP 平成21年秋 午後問2:方法1(単純な照合)と方法2(判定文字とスキップ数の表を使う照合)。設問2でHIPOPOTAMUSのスキップ数(エ=10、オ=6)、設問3で比較回数(α=12回、β=8回)
FE 平成27年秋 午後問8:関数BMMatch(Boyer-Moore-Horspool法)。設問1はa=PatLen・b=PatLen-I、設問2はc=3・d=7・e=9、設問3は走査順を逆にすると「含まれているのに−1を返す」不具合
FE 令和7年度 科目B 問4(IPA公開問題):力まかせ法で並びの一致箇所を数える関数search。条件式が真となる回数を問い、正解は「ク」(8回)
| 手順 | 比較 | 結果 | 判定文字とずらし幅 | 次の末尾位置 |
|---|---|---|---|---|
| 1 | Text[4]=B と Pat[4]=B | 一致 | — | 4 |
| 2 | Text[3]=B と Pat[3]=A | 不一致 | B → 4 | 8 |
| 3 | Text[8]=A と Pat[4]=B | 不一致 | A → 1 | 9 |
| 4 | Text[9..6] と Pat[4..1] | 全て一致 | — | 位置6で終了 |
BM法のスキップ表を30秒で作る3ステップ
スキップ表(ずらし幅の表)は、3つの手順で機械的に埋まります。
午後で長い問題文を見て身構えても、最初に紙の隅へこの表を書き出してしまえば残りはただのトレース作業だった、というのが受験時の実感でした。
スキップ表の作成3ステップ
長さmを数える
パターンの文字数を確定する
末尾以外の文字
末尾からの距離を記入。複数回出るなら末尾に近い方
残りは全部m
末尾だけに出る文字と、出現しない文字
②が減点の集中ポイント。距離の起点は必ず末尾
同じ文字が複数回現れたら、末尾に近い方の距離を採用します。
遠い方で上書きすると本来より大きく飛び、一致箇所を飛び越えて「見つからない」と誤判定する。
FE平成27年秋 設問3は、この上書き順序の誤りをそのまま不具合として問いました。
📊 スキップ表の実例(FE平成27年秋/AP平成21年秋)
| パターン | 判定文字 | スキップ数 | 根拠 |
|---|---|---|---|
| ACAB(m=4) | A | 1 | 末尾に近い3文字目を採用(4-3) |
| ACAB(m=4) | B | 4 | 末尾だけに出現 → m |
| ACAB(m=4) | C | 2 | 2文字目(4-2) |
| ACAB(m=4) | その他 | 4 | 出現しない → m |
| HIPOPOTAMUS(m=11) | H | 10 | 1文字目のみ(11-1) |
| HIPOPOTAMUS(m=11) | P | 6 | 3文字目と5文字目 → 近い5文字目(11-5) |
【確認テスト】KMP法・BM法の理解度チェック
比較方向とずらし幅の根拠、その両方を同時に確認する問題です。
Q. BM法(ボイヤー・ムーア法)による文字列探索の説明として、最も適切なものはどれか。
- A. パターンの先頭から順に比較し、一致していた部分の情報を利用して次の比較開始位置を決める
- B. 探索範囲の中央の要素と目的値を比較し、範囲を半分に絞り込むことを繰り返す
- C. パターンの末尾の文字から先頭方向へ比較し、不一致となったテキスト側の文字がパターン内のどこに現れるかに応じて、パターンを一度に複数文字ずらす
- D. キーから格納位置を関数で直接計算し、1回の計算で目的のデータへ到達する
正解と解説を見る
正解:C
解説:
BM法の定義は「末尾から比較する」「不一致となったテキスト側の文字でずらし幅を決める」の2要素で構成されます。Cはこの両方を含んでいるため正解。なおAはKMP法としては完全に正しい説明で、BM法の説明として選ぶと誤りになる、という構造の問題。この対比で2手法をセットで覚えてしまうのが効率的です。
Aが不正解の理由:KMP法の説明。比較方向を先頭からとしており、BM法とは逆になっている
Bが不正解の理由:2分探索法の説明。整列済みという前提が必要で、文字の並びの照合には使えない
Dが不正解の理由:ハッシュ法の説明。「高速な探索」という連想からの誤答を誘う選択肢
KMP法・BM法の関連用語ネットワーク
2分探索法(バイナリサーチ)は整列済みという前提が必要で、文字の並びには使えません。だから文字列探索は範囲を半分に絞るのではなく、ずらし幅を稼ぐ戦略へ進んだ、と押さえておくと関連分野がつながります。
📊 関連用語マップ
| カテゴリ | 関連用語 |
|---|---|
| 前提知識 | データ構造(配列・リスト)、線形探索法(力まかせ法の発想の元) |
| 関連用語 | 2分探索法、整列アルゴリズム(ソート)、オーダー記法 |
| 発展 | ハッシュ表(ハッシュ法)、全文検索と索引(インデックス) |