Rabin–Karp algorithm: Difference between revisions

Revision as of 07:16, 14 November 2005

Revision as of 07:23, 14 November 2005

Line 27:

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

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

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

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

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

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

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

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

'''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.