KMP法（Knuth-Morris-Pratt）のテキスト長n、パターン長mに対する時間計算量は？ 2025.09.22 KMP法（Knuth-Morris-Pratt）のテキスト長n、パターン長mに対する時間計算量は？ O(n*m) O(n + m) O(n log m) O(n*m^2) KMP法はパターンの接頭辞関数（failure function）をO(m)で前処理し、テキストを走査するときに部分一致情報を利用して巻き戻しを繰り返さずマッチングを進めます。その結果、全文検索の照合処理はO(n)、前処理と合わせて総計O(n+m)の時間でパターン検索が可能となります。 クイズタグ: 競技プログラミング関連記事 競技プログラミングクイズ！【問題 全10問・答え付き】 | 2025年09月版
