Talk:Rabin–Karp algorithm: Difference between revisions

Revision as of 00:18, 30 March 2008

Revision as of 21:21, 21 April 2008

Line 1:

==Extending the algorithm==

I think it would be nice if the article discussed extending the algorithm for 2 dimensional pattern matching, as well as giving some optimizations in the case of having varying string lengths for multi-pattern matching case.

=== Concerns ==

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. This is why I reverted it to be ''hash(s[1...m])''.

Line 19 ⟶ 20:

:I agree with you. We are assuming m ≤ n, and if [1..n] is used, the algorithm won't work, because it'd be trying to compare hashes of strings of length ''n'' to hashes of strings of length ''m''. [[User:Dcoetzee|Deco]] 21:41, 23 May 2005 (UTC)

== Line 8 of the mulimulti-pattern-search pseudo-code seems wrong to me ==

Quote: if s[i..i+m-1] = a substring with hash hs