文字列照合アルゴリズム（BM法・KMP法）とは？
文字列照合アルゴリズム（BM法・KMP法）とは、長い文章の中から目的の文字列が現れる位置を探す手法。1文字ずつずらして比べる力任せ法に対し、不一致が起きたときにどれだけ大きくずらしてよいかを前もって計算しておき、比較回数を減らす。
もじれつしょうごうあるごりずむ
文字列照合アルゴリズム（BM法・KMP法）の意味
長い文章の中から目的の文字列が現れる位置を探す手法。1文字ずつずらして比べる力任せ法に対し、不一致が起きたときにどれだけ大きくずらしてよいかを前もって計算しておき、比較回数を減らす。
文字列照合アルゴリズム（BM法・KMP法）の具体例
BM法は探す文字列の末尾から比較し、不一致になった文字が探す文字列に含まれないなら一気にその長さ分ずらす。エディタの全文検索や、ウイルス定義のパターンとの照合などで使われる。
文字列照合アルゴリズム（BM法・KMP法）は試験でどう引っ掛けられる？
力任せ法の最悪計算量は文章長と検索文字列長の積に比例するが、普通の文章では平均的に十分速い。改良手法にも前処理の手間があるため、短い検索では必ずしも得にならない。
文字列照合アルゴリズム（BM法・KMP法）と関連する用語
最終更新：2026-08-25／解説は資格暗記が独自に作成しています。 過去問の出典は各問題に記載のとおりです。