User talk:Chang.h.kim

From Wikipedia, the free encyclopedia

[edit] RK string search algorithm

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.