KMP法（Knuth–Morris–Pratt）完全解説：原理・実装・応用と最適化

2025年12月12日 最終更新日時 : 2025年12月12日 エバープレイ編集部

KMP法とは

KMP法は、1977年にDonald Knuth、Vaughan Pratt、James H. Morrisによって発表された文字列検索アルゴリズムで、テキスト中からパターンを線形時間で探索する手法です。ナイーブな探索法が最悪計算量O(nm)になるのに対し、KMPは前処理で「失敗関数（接頭辞関数）」を計算することで、探索時に既に比較した情報を再利用し、総時間をO(n + m)に抑えます（n: テキスト長、m: パターン長）。

基本アイデア（直感）

パターンのある位置まで一致したが、次の比較で不一致になった場合、ナイーブ法ではパターンを1文字ずつずらして再比較します。KMPは、パターン自身の内部に存在する「一致した接尾辞が同時に一致しうる接頭辞」を利用し、ずらし量を最適化します。これにより無駄な比較を避け、同じテキスト位置を何度も見ることがなくなります。

接頭辞関数（pi 配列、lps）の定義と直感

パターン P[0..m-1] に対して、pi[i] は部分文字列 P[0..i] の真の接頭辞かつ接尾辞として最大の長さを返します。言い換えると、P[0..pi[i]-1] と P[i-pi[i]+1..i] が一致する最大の長さです。pi 配列はパターンの自己重複構造（border）を表現しており、検索時に次の比較位置を決めるために使われます。

pi 配列の計算（線形時間アルゴリズム）

pi 配列は以下の手順で線形時間で求められます。i を左から右に進め、現在までの最長一致長を k として維持します。不一致が起きたら k を pi[k-1] に遡らせ、次の一致を試みます。これにより各位置は定数回しか処理されず、計算量はO(m)になります。

  • 初期化: pi[0] = 0
  • i を 1 から m-1 まで増やす
  • k = pi[i-1] を参照し、P[k] と P[i] を比較
  • 不一致なら k = pi[k-1] を繰り返す
  • 一致すれば k を 1 増やして pi[i] = k

擬似コード:

function compute_pi(P):
  m = length(P)
  pi = array of zeros size m
  k = 0
  for i from 1 to m-1:
    while k > 0 and P[k] != P[i]:
      k = pi[k-1]
    if P[k] == P[i]:
      k = k + 1
    pi[i] = k
  return pi

実際の検索アルゴリズム

テキスト T[0..n-1] に対して、パターン P とその pi を用いて左から右へ1回走査します。現在まで一致した文字数を q とし、T の各文字を処理する際に P[q] と比較します。不一致が起きたら q を pi[q-1] に遡らせて再試行し、一致すれば q を増やします。q が m に達したら一致位置を発見し、1回の一致を報告して q を pi[q-1] に更新して続けます。

  • 初期化: q = 0
  • for i from 0 to n-1: while q > 0 and P[q] != T[i]: q = pi[q-1]; if P[q] == T[i]: q++ ; if q == m: report occurrence at i-m+1; q = pi[q-1]

このアルゴリズムも各文字について遡りはあるが総和でO(n)の遷移しか起きないため、全体でO(n + m)の時間で完了します。

計算量とメモリ

時間計算量は前処理でO(m)、検索でO(n)、合わせてO(n + m)です。追加の記憶領域としては pi 配列が O(m) 必要です。定数倍のオーバーヘッドが小さく、実用上の性能も良好です。

実装上の注意点

  • インデックスの基準に注意すること（0始まりと1始まり）。ここでは0始まりを使う例を示しました。
  • Unicode文字列を扱う場合、バイト列ではなくコードポイント列や適切なエンコーディングを扱うこと。UTF-8のままバイト単位で処理するとマルチバイト文字が壊れる恐れがあります。
  • 言語の標準ライブラリに最適化された検索がある場合はそれを使う選択肢もあるが、部分一致や繰り返し検索を大量に行う場合はKMPが有効なことが多いです。

応用例と派生的な利用法

  • 文字列検索（ログ解析、テキストエディタ、検索エンジンの一部処理）
  • バイオインフォマティクスにおける配列パターン検索（短いモチーフ検索など）
  • 最短接尾／接頭辞問題の解析、最小周期の計算（文字列の最小周期は m - pi[m-1] で求められる）
  • 文字列の最短回文補完など。たとえば文字列 S の逆順を使って特定の接合をすれば最短先頭挿入で回文にする問題に応用できる
  • オートマトン化して複数パターン検索の一部要素として使うことも可能だが、複数パターンそのものの高速検索にはAho-Corasick の方が一般的

KMPと他アルゴリズムの比較

  • ナイーブ法: 最悪O(nm)、平均でも劣る場合がある。KMPは最悪でも線形。
  • Boyer-Moore: 多くの実用ケースで非常に高速。アルファベットが大きい場合やランダムデータに強いが、最悪時の解析は複雑。KMPは安定して線形。
  • Zアルゴリズム: pi とは別だが同様に自己一致構造を利用して線形時間で動作する。Z関数はテキスト結合でパターン検索にも使える。

よくある誤解と落とし穴

  • pi 配列が示すのは「重複の長さ」であって、必ずしも次の一致位置の直接のシフト量がそのまま意味を持つとは限らない。正しい遷移は pi を使って計算される。
  • 実装ミスの多くはインデックスのずれと pi 更新ロジックの誤りに起因するため、単体テストで短いパターンと境界条件をチェックすること。
  • ユニコードの扱い、バイナリデータでの比較、空文字列や1文字パターンなどの特殊ケースを考慮すること。

証明の概略（線形性の理由）

pi 配列の計算と検索の両方で用いられる遡り操作は、各ステップで k を pi[k-1] に移すため、一度遡った分は二度と同じ位置について遡らないという性質があります。各文字位置は最大1回インクリメントされ、遡りも総計で最大m回（前処理）や最大n回（検索）しか発生しないため、合計でO(n + m)になります。

実務での使い方例（短いチュートリアル）

1) パターンの pi 配列を先に計算しておく。2) テキストを左から走査して一致長 q を更新。3) 一致検出時に位置を記録し q を更新して続行。ログファイルからエラーパターンを連続的に抽出するような処理に適しています。またWebサービスでストリームデータに対して部分文字列検出を行う際は、状態 q を保存しておけばストリーム継続中にKMPを使えます。

まとめ

KMP法はパターン検索の基本アルゴリズムの一つで、自己一致構造を利用して無駄な比較を排除する点が特徴です。実装はやや注意が必要ですが、正しく実装すれば安定して線形時間で動作し、多くの実用課題に応用できます。パフォーマンスが重要な場面ではBoyer-MooreやAho-Corasickなどと使い分けると効果的です。

参考文献

カテゴリー
IT
前の記事
ウィリアム・ワイラー：巨匠の生涯と名作 — 映画史に残る演出術と代表作の深層分析New!!
2025年12月12日
次の記事
ジョージ・キューカー──「女優の監督」が築いたハリウッド黄金期の美学と遺産New!!
2025年12月12日