Rabin–Karp algorithm: Difference between revisions

Revision as of 02:02, 11 March 2005

Revision as of 16:03, 11 April 2005

Line 77:

Other algorithms can search for a single pattern in time order O(n), hence they will search for k patterns in time order O(n*k). The variant Rabin-Karp above will still work in time order O(n) in the best and average case, because a hash table allows to check whether or not substring hash equals any of the pattern hashes in time order of O(1). We can also ensure O(''mn''log ''k'') time in the worst case, where ''m'' is the length of the longest of the ''k'' strings, by storing the hashes in a [[self-balancing binary search tree]] instead of a hash table.

==External linksReferences==

* Karp and Rabin's original paper: Karp, Richard M.; Rabin, Michael O. (March 1987). "[http://www.research.ibm.com/journal/rd/312/ibmrd3102P.pdf KarpEfficient randomized pattern-matching algorithms]". ''IBM Journal of Research and RabinDevelopment''s original'''31''' paper](2), 249-260.

[[Category:Algorithms on strings]]