アルゴリズム・データ構造図鑑 · 基礎から応用へ

KMP法:一致した接頭辞を失敗後も利用する

接頭辞関数で戻り先を求め、テキストを巻き戻さずに重なる出現も検索する。

この記事をロゲイアに質問する確認問題3問に進むこれまでの誤答を復習する

更新日

この記事の目次
  1. 一致した長さを状態にする
  2. ababacの戻り先を追う
  3. 重なる一致と線形時間
  4. 空パターンと表現を決める
  5. この記事をロゲイアに質問する理解を確かめる

一致した長さを状態にする

KMP法は長さmのパターンを前処理し、長さnのテキストを一方向へ読み進めます。ここでは接頭辞関数πを使う版を考えます。π[i]はパターンの位置iまでの部分文字列について、全体より短い接頭辞であり同時に接尾辞でもあるものの最大長です。検索中の状態jは、これまで読んだテキストの末尾と一致しているパターンの接頭辞の長さです。不一致が起きても、その一致の内部にある接頭辞・接尾辞の関係を利用できるので、テキストを最初から比べ直す必要がありません。

ababacの戻り先を追う

パターンababacの接頭辞関数は[0,0,1,2,3,0]です。ababaまで一致し、次の文字が期待するcではなくbだった場合、j=5からπ[4]=3へ戻して、同じテキスト文字をパターンの位置3にあるbと比べます。これはテキスト末尾のabaがパターン先頭のabaでもあるためです。jを0へ戻してテキスト位置もやり直す方法とは異なります。一致済みの情報をどこまで再利用できるかが配列に保存されているので、戻る長さを勘で選ぶ必要はありません。

重なる一致と線形時間

パターンabaはテキストababaの位置0と2へ現れます。一致が完成したあとjをπ[m−1]へ戻せば、末尾aを次の一致の先頭として再利用できます。接頭辞関数の構築も検索も、jが増える回数と減る回数を合計して線形に評価でき、時間O(n+m)、補助領域O(m)です。不一致のたびにループが動くことだけを見てO(nm)だと考えると、テキスト位置が戻らずjの増加にも上限がある点を見落とします。出現を全件出すなら出力件数の費用も含めます。

空パターンと表現を決める

空パターンがすべての境界で一致するのか、入力エラーなのかは検索APIの仕様として決めます。バイト列、Unicodeのコードポイント、言語が使うコード単位では、返す位置の意味も変わります。大文字小文字の同一視や正規化が必要なら、それらを施した列に対して検索し、元の位置へ戻す対応を考えます。アルファベットごとの遷移表を持つDFA版もありますが、ここで説明した長さmの接頭辞配列とは前処理の領域が異なります。実装方式を明記して比較しましょう。

読了と問題の結果を、言語ごとにこのブラウザへ保存します。

コースの順番に沿って学ぶ

CS基礎を固める · STEP 10

学習コースから次を選ぶ