文字列照合アルゴリズムとは？
文字列照合アルゴリズムとは、長さnの本文から長さmのパターンを探す手法の総称。1文字ずつずらして比較する素朴法は最悪O(nm)だが、KMP法は不一致時にパターン内部の重なりを利用し、BM法はパターンの末尾から比較して一気にずらすことで平均的に高速化する。
もじれつしょうごうあるごりずむ
文字列照合アルゴリズムの意味
長さnの本文から長さmのパターンを探す手法の総称。1文字ずつずらして比較する素朴法は最悪O(nm)だが、KMP法は不一致時にパターン内部の重なりを利用し、BM法はパターンの末尾から比較して一気にずらすことで平均的に高速化する。
文字列照合アルゴリズムの具体例
マルウェア対策ソフトの定義パターン照合や、grepのような検索コマンドの内部処理。BM法は本文中に現れない文字に当たるとパターン長ぶんまとめてずらせるため、英文のような文字種の多いデータで効果が大きい。
文字列照合アルゴリズムは試験でどう引っ掛けられる？
BM法は「平均的に速い」だけで最悪計算量は改善されない。ハッシュ値で比較するRabin-Karp法は複数パターンの同時検索に強い、といった得意分野の違いを取り違えないこと。
文字列照合アルゴリズムと関連する用語
最終更新：2026-08-25／解説は資格暗記が独自に作成しています。 過去問の出典は各問題に記載のとおりです。