Talk:Rabin–Karp algorithm: Difference between revisions

Revision as of 22:12, 3 January 2010

Revision as of 09:54, 22 May 2010

Line 29:

:I need to correct myself. The code is ok, although I don't quite get how the rolling hash would compare varying key-lengths. I improved the code indentation so the code is more readable [[User:ISee|iSee]]

::Are you sure this is OK? I just came to the talk page with exactly the same concern: line 8 doesn't make sense. We *know* that "s[i..i+m-1] = a substring with hash hs" because we set hs to satisfy this on the last line of the previous iteration. I think what line 8 is *meant* to do is check that s[i..i+m-1] is a member of subs -- i.e. do a string match to ensure this is not a hash collision. *Something* is wrong because when returning at line 9, nothing has checked against hash collisions. (As a side-issue, the nested if statements seem unnecessary and would be cleaner with an "and", and the braces around the function are inconsistent with indentation-nesting and with the rest of the article.)

I think the pseudocode could be changed to the following, which I'm doing now as I'm confident it's wrong currently.

'''function''' RabinKarpSet(''string'' s[1..n], ''set'' of ''string'' subs, m):

''set'' hsubs := emptySet

'''for each''' sub '''in''' subs

insert hash(sub[1..m]) into hsubs

hs := hash(s[1..m])

'''for''' i '''from''' 1 '''to''' n-m+1

'''if''' hs ∈ hsubs '''and''' s[i..i+m-1] ∈ subs

'''return''' i

hs := hash(s[i+1..i+m])

'''return''' not found

[[User:Jameshfisher|Jameshfisher]] ([[User talk:Jameshfisher|talk]]) 09:54, 22 May 2010 (UTC)

==No worst case==