Content deleted Content added
PerVognsen (talk | contribs) Suggestions |
|||
Line 35:
Rabin-Karp simply doesn't make sense in the worst case, because the whole idea of hashing requires randomization and can only work in expectation (or with high probability).
:That's true. My mistake. [[User:Dcoetzee|Deco]] 02:51, 31 July 2005 (UTC)
== Suggestions ==
Firstly, it seems like
'''1''' '''function''' RabinKarp(''string'' s[1..n], ''string'' sub[1..m])
'''2''' hsub := hash(sub[1..m])
'''3''' hs := hash(s[1..m])
'''4''' '''for''' i '''from''' 1 '''to''' n
'''5''' '''if''' hs = hsub
'''6''' '''if''' s[i..i+m-1] = sub
'''7''' '''return''' i
'''8''' hs := hash(s[i+1..i+m])
'''9''' '''return''' not found
could be shortened to
'''1''' '''function''' RabinKarp(''string'' s[1..n], ''string'' sub[1..m])
'''2''' hsub := hash(sub[1..m])
'''3''' '''for''' i '''from''' 1 '''to''' n
'''7''' hs := hash(s[i..i+m-1])
'''4''' '''if''' hs = hsub
'''5''' '''if''' s[i..i+m-1] = sub
'''6''' '''return''' i
'''7''' '''return''' not found
Aside from being a line shorter, I find this more clearly displays what hs is for any given iteration. The same comment applies to the other example of multi-pattern matching.
On the topic of the multi-pattern matching code, I think it is worth noting in both the code and the surrounding discussion the possibility for hash table collisions. As it stands, one might wrongly infer from the code that the only possibility is that a hash table either has no entry or a single entry for any given hash code.
| |||