Skip to content

HTTPS clone URL

Subversion checkout URL

You can clone with HTTPS or Subversion.

Download ZIP
branch: master
Fetching contributors…

Cannot retrieve contributors at this time

32 lines (22 sloc) 0.718 kb

Rabin–Karp algorithm

Rabin–Karp algorithm is a string searching algorithm created by Michael O. Rabin and Richard M. Karp in 1987 that uses hashing to find any one of a set of pattern strings in a text (c) Wiki

Algorithm description

Wiki

Benchmarks

n         = 50000
string    = 'hello world'
substring = 'world'

Benchmark.bm do |x|
  x.report { n.times { string.rk_search('world') } }
  x.report { n.times { string.scan('world') } }
end

results:

    user     system      total        real
0.360000   0.000000   0.360000 (  0.358861)
0.120000   0.000000   0.120000 (  0.114930)

TODO:

Write better benchmarks

Jump to Line
Something went wrong with that request. Please try again.