ようこそ ゲスト さん、新規登録（無料）して気になる疑問を解決しませんか？
はじめての方へ｜FAQ

質問
質問者：systam 文字列探索ＫＭＰ法の計算量について。
困り度：
  • すぐに回答を！
 ＫＭＰ法の計算量についての質問です。
(1)計算量がO(M+N)になるのは何故か？
(2)この計算量は漸近的には改善できない最善のものであると記載されているが、それは何故か？
※テキストの長さ＝Ｎ、キー(パターン)の長さ＝Ｍ

参考書を見て勉強していたのですが、計算量については省略されてしまっていたために不明なままです。どなたかご存知の方がいらっしゃいましたらよろしくお願いします。
質問投稿日時：08/12/16 23:06
質問番号：4561415
この質問に対する回答は締め切られました。
最新から表示｜回答順に表示｜良回答のみ表示

回答

良回答20pt
回答者：mtaka2 > (1)

メインな文字列の検索処理についてみると、テキストの個々の文字について1回しか比較を行いませんから、O(N)になります。
ですが、KMPではその前にテーブルを作る必要があります。こちらの処理はO(M)になります。
両方あわせるとO(M+N)です。

> (2)
文字列検索をするためには、「テキストの全ての文字を調べる」必要があり、そのためには最低でもO(N)は必要です。
O(N)より小さい、O(log N) や O(√N) では、全ての文字を調べることができません。
同様に、検索パターンの方も全ての文字を調べる必要があるから、こちら側では最低でもO(M)が必要です。
つまり、両方あわせると、最低でもO(M+N)は必要、ということになります。
種類：回答
どんな人：経験者
自信：自信あり
回答日時：08/12/17 23:11
回答番号：No.2
この回答へのお礼テーブルを作る処理と比較の処理を別々に考えたら納得できました。

(2)についてもとても分かりやすい説明ありがとうございます。

解決できました！

回答

良回答10pt
回答者：Tacosan (1) はそれぞれの文字列をさすポインタがどのように動くかを見ていくのがよいかと. ポインタがあともどりしなければ O(m+n) になりますよね.
(2) テキストとキーが最後でマッチする場合を考えるのかな?
種類：アドバイス
どんな人：一般人
自信：参考意見
回答日時：08/12/17 01:21
回答番号：No.1
この回答へのお礼ポインタの動きを見ていけばよいのですね。ありがとうございます。
最新から表示｜回答順に表示｜良回答のみ表示
このページのトップへ