Rabin–Karp algorithm: Difference between revisions

Revision as of 22:28, 6 November 2005

Revision as of 07:16, 14 November 2005

Line 27:

'''1''' '''function''' RabinKarp(''string'' s[1..n], ''string'' sub[1..m])

'''2''' hsub := hash(sub[1..m])

'''3''' hs'''for''' :=i '''from''' hash(s[1..m]) '''to''' n

'''4''' '''for''' i '''from''' 1 '''to'''hs n:= hash(s[i..i+m-1])

'''5''' '''if''' hs = hsub

'''6''' '''if''' s[i..i+m-1] = sub

'''7''' '''return''' i

'''8''' '''return''' not hs := hash(s[i+1..i+m])found

'''9''' '''return''' not found

Lines 2, 3, and 6 each require [[Big-O notation|Ω]](m) time. However, lines 2 and 3 are only executed once, and line 6 is only executed if the hash values match, which is unlikely to happen more than a few times. Line 5 is executed ''n'' times, but only requires constant time. We now come to the second problem: line 8.