Rabin-Karp implementation in Ruby
Ruby
Switch branches/tags
Nothing to show
Latest commit bb10f74 Apr 9, 2012 @nashby Merge pull request #1 from lest/patch-1
add source to Gemfile
Permalink
Failed to load latest commit information.
Gemfile add source to Gemfile Apr 9, 2012
Gemfile.lock initial Apr 7, 2012
README.md README Apr 7, 2012
rabin-karp.rb initial Apr 7, 2012

README.md

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