文字列照合アルゴリズム（KMP法・BM法）とは？
文字列照合アルゴリズム（KMP法・BM法）とは、長い文字列から部分文字列を探す処理を、素朴な総当たりのO(nm)より速くする手法。KMP法は照合失敗時に既に一致した部分の情報から次の比較開始位置を決め、BM法はパターンの末尾から比較して不一致文字に応じてパターンを大きくずらす。
もじれつしょうごうあるごりずむ
文字列照合アルゴリズム（KMP法・BM法）の意味
長い文字列から部分文字列を探す処理を、素朴な総当たりのO(nm)より速くする手法。KMP法は照合失敗時に既に一致した部分の情報から次の比較開始位置を決め、BM法はパターンの末尾から比較して不一致文字に応じてパターンを大きくずらす。
文字列照合アルゴリズム（KMP法・BM法）の具体例
検索対象n文字・パターンm文字のとき、素朴法は毎回1文字ずつずらすが、BM法はパターン中に現れない文字で不一致になればm文字分まとめて飛ばせる。実用の文字列検索コマンドやエディタの検索がこの系統を使っている。
文字列照合アルゴリズム（KMP法・BM法）は試験でどう引っ掛けられる？
KMP法は最悪でもO(n+m)を保証する一方、実際の平均性能はBM法のほうが速いことが多い。またBM法は前処理でパターン側の表を作るため、パターンが頻繁に変わる用途では前処理コストが効いてくる。
文字列照合アルゴリズム（KMP法・BM法）と関連する用語
最終更新：2026-08-25／解説は資格暗記が独自に作成しています。 過去問の出典は各問題に記載のとおりです。