文字列探索アルゴリズム（KMP法・BM法）とは？

文字列探索アルゴリズム（KMP法・BM法）とは、長い文字列の中から特定のパターンが現れる位置を見つける手法。単純な総当たりは最悪O(nm)だが、KMP法は不一致時にパターン内の一致情報を使って後戻りをなくしO(n+m)、BM法はパターンの末尾から比較しずらし幅を大きく取ることで平均を高速化する。

もじれつたんさくあるごりずむ

応用情報技術者試験の頻出用語／テクノロジ系／別名：文字列探索アルゴリズム、KMP法・BM法、KMP法、BM法

文字列探索アルゴリズム（KMP法・BM法）の意味

長い文字列の中から特定のパターンが現れる位置を見つける手法。単純な総当たりは最悪O(nm)だが、KMP法は不一致時にパターン内の一致情報を使って後戻りをなくしO(n+m)、BM法はパターンの末尾から比較しずらし幅を大きく取ることで平均を高速化する。

ログから特定の文字列を抽出する処理で、パターンが長いほどBM法の一致しない文字によるスキップが効き、比較回数が総当たりより大幅に減る。実装の複雑さと入力規模を見て、短い入力なら単純法で十分という判断も現実的。

BM法は「最悪計算量が速い」のではなく平均が速い手法で、最悪ではO(nm)になり得る。またKMP法は前処理でパターンの表を作る必要があり、この前処理コストO(m)を無視した比較は不正確。

最終更新：2026-08-25／解説は資格暗記が独自に作成しています。過去問の出典は各問題に記載のとおりです。