【けーえむぴーほう】
KMP法 とは？
最終更新:
💡 一致済みの情報を使い、文字列の比較をやり直す量を減らす
文字列の完全一致検索で、既に一致した部分の情報を利用して比較のやり直しを減らすアルゴリズム。パターンを前処理し、テキスト長n、パターン長mに対してO(n+m)時間で検索できる。テキスト側の位置を巻き戻さずに進められる。
📌 このページのポイント
- 検索するパターンから、再利用できる部分一致の情報を作る
- 不一致時はパターン側の比較位置を戻す
- テキスト側の比較位置は巻き戻さない
- 前処理を含む時間はO(n+m)、表の領域はO(m)
ひよこ 素朴な文字列検索との違いは？
ペンギン先生 候補の開始位置を一文字ずつずらし、先頭から比較し直す方法では、同じ文字を何度も比べることがある。この方法は一致済みの部分を利用し、必要な比較だけを続けるんだ。
ひよこ 失敗関数って何？
ペンギン先生 不一致の後、パターンのどこから比較を続けるかを決める情報だよ。表の表現には違いがある。一つの形は、各接頭辞について、それ自身を除いて先頭と末尾が同じになる最長部分の長さを記録するもの。ABABCなら順に0、0、1、2、0になるよ。
ひよこ 具体的にはどこから再開するの？
ペンギン先生 テキストABABABCにパターンABABCを先頭から重ねると、ABABまで一致し、次のCとテキストのAが不一致になる。一致済みのABABの先頭と末尾はAB。そこでこの2文字を再利用し、同じテキストのAと、パターンの3文字目Aを比較する。テキストを巻き戻さず、先頭を2文字ずらした位置で一致が見つかるんだ。
ひよこ いつでも速いの？
まとめ：ざっくりこれだけ覚えればOK！
「クヌース・モリス・プラット法」って出てきたら「一致済みの情報を使い、文字列の比較をやり直す量を減らす」と思えばだいたいOK！
📖 おまけ：英語の意味
「Knuth–Morris–Pratt Algorithm」 ＝ クヌース・モリス・プラット法
💬 Donald E. Knuth、James H. Morris Jr.、Vaughan R. Prattの姓をつないだ名前。1977年の論文Fast Pattern Matching in Stringsで説明されているよ。