User talk:Chang.h.kim
Appearance
RK string search algorithm
[edit]You wrote:
In the pseudocode of the RK string search algorithm, if hs is given as hash(s[1..n]), the algorithm can not detect a target pattern which occurs on the first m bytes of a given text.
Your point on the case where m is larger than n is correct, but I thought that such a parameter range check can be assumed to have been performed prior to calling the function.
Btw, what do you think about the following sentence which is quoted from the sentence right beneath the pseudocode. "Lines 2,3, and 6 each require omega(m) time."
If you still think hs := hash(s[1...n]) is correct, why don't you modify the above sentence too?
Looking over the code I think you are right (though the pseudocode is dangerous and should be rewritten to contain checks). I'll return it into your version.