Skip to content
This repository

HTTPS clone URL

Subversion checkout URL

You can clone with HTTPS or Subversion.

Download ZIP

Rabin-Karp implementation in Ruby

branch: master

Fetching latest commit…

Octocat-spinner-32-eaf2f5

Cannot retrieve the latest commit at this time

Octocat-spinner-32 Gemfile
Octocat-spinner-32 Gemfile.lock
Octocat-spinner-32 README.md
Octocat-spinner-32 rabin-karp.rb
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

Something went wrong with that request. Please try again.