Jump to content

User talk:Chang.h.kim

Page contents not supported in other languages.
From Wikipedia, the free encyclopedia

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.