KMP（Knuth–Morris–Pratt）文字列検索アルゴリズムにおけるパターンの部分一致テーブル（失敗関数）の前処理の時間計算量はパターン長 m を用いてどれか？ 2026.01.31 KMP（Knuth–Morris–Pratt）文字列検索アルゴリズムにおけるパターンの部分一致テーブル（失敗関数）の前処理の時間計算量はパターン長 m を用いてどれか？ O(n)（テキスト長に依存） O(m) O(nm) O(m log m) KMP アルゴリズムではパターン（長さ m）に対して接頭辞・接尾辞の一致を利用する失敗関数（lps や prefix 関数）を前処理で構築します。この前処理はパターン長 m のみを参照し、線形時間で計算できるため O(m) です。本体の検索はテキスト長 n の処理を加えて O(n + m) となります。 クイズタグ: アルゴン関連記事 アルゴンクイズ！【問題 全10問・答え付き】 | 2026年01月版
