文字列探索（KMP法・BM法）とは？
文字列探索（KMP法・BM法）とは、長い文章の中から特定の文字列が現れる位置を見つける処理。先頭から1文字ずつずらす素朴な方法に対し、KMP法は不一致になった位置までの一致情報を再利用し、BM法は末尾から照合して不一致文字に応じて大きくずらすことで高速化する。
もじれつたんさく
文字列探索（KMP法・BM法）の意味
長い文章の中から特定の文字列が現れる位置を見つける処理。先頭から1文字ずつずらす素朴な方法に対し、KMP法は不一致になった位置までの一致情報を再利用し、BM法は末尾から照合して不一致文字に応じて大きくずらすことで高速化する。
文字列探索（KMP法・BM法）の具体例
「ABCABD」を探す途中でDのところが不一致になったとき、素朴な方法は1文字ずらして先頭から比べ直す。KMP法は直前まで一致していた「ABC」の情報から、比較済みの文字を読み直さずに済む位置まで一気にずらす。
文字列探索（KMP法・BM法）は試験でどう引っ掛けられる？
BM法は末尾から比べるため、探したい文字列が長いほど1回のずれ幅が大きくなり有利になる。ただし前処理として表を作る必要があり、対象が短い場合は素朴な方法のほうが速いこともある。
文字列探索（KMP法・BM法）と関連する用語
最終更新：2026-08-25／解説は資格暗記が独自に作成しています。 過去問の出典は各問題に記載のとおりです。