文字列探索ＫＭＰ法の計算量について。

質問

ＫＭＰ法の計算量についての質問です。
(1)計算量がO(M+N)になるのは何故か？
(2)この計算量は漸近的には改善できない最善のものであると記載されているが、それは何故か？
※テキストの長さ＝Ｎ、キー(パターン)の長さ＝Ｍ

参考書を見て勉強していたのですが、計算量については省略されてしまっていたために不明なままです。どなたかご存知の方がいらっしゃいましたらよろしくお願いします。

回答No.2

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)は必要、ということになります。

お礼

テーブルを作る処理と比較の処理を別々に考えたら納得できました。

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

解決できました！

回答No.1

Tacosan

(1) はそれぞれの文字列をさすポインタがどのように動くかを見ていくのがよいかと. ポインタがあともどりしなければ O(m+n) になりますよね.
(2) テキストとキーが最後でマッチする場合を考えるのかな?

お礼

ポインタの動きを見ていけばよいのですね。ありがとうございます。