【けーえむぴーほう】
KMP法 とは？
💡 失敗からも学ぶ、賢い文字列サーチ
📌 このページのポイント
- パターンの部分一致情報（失敗関数）を前処理で構築する
- 不一致時に先頭に戻らず、部分一致分だけスキップして効率化
- テキスト長n、パターン長mに対してO(n+m)で検索できる
- テキストエディタの検索機能やウイルススキャンの基礎技術
ペンギン先生 普通の方法だと不一致が起きたら1文字ずらしてまた最初から比較し直すよね。KMP法は「ここまでは一致していた」という情報を使って、無駄な比較をスキップするんだよ。
ひよこ 失敗関数って何のこと？
ペンギン先生 ひよこ それってどれくらい速くなるのかな？
ペンギン先生 最悪ケースでもO(n+m)が保証されるのが強みだよ。素朴な方法だと最悪O(nm)になるから、長いテキストで繰り返しの多いパターンを検索するときに圧倒的な差が出るんだ。
ひよこ 実際どんなところで使われてるの？
📖 おまけ：英語の意味
「Knuth-Morris-Pratt Algorithm」 ＝ クヌース・モリス・プラット法
💬 3人の研究者Knuth、Morris、Prattの頭文字を取ってKMPと呼ばれるんだよ