Create a gist now

Instantly share code, notes, and snippets.

@danielrsmith /test.rb Secret
Last active Aug 29, 2015

What would you like to do?
require 'digest'
def RabinKarp(haystack, needle)
hneedle = Digest::MD5.hexdigest needle
hhaystack = Digest::MD5.hexdigest haystack[0..needle.length]
for i in 1..haystack.length-needle.length+1
return i if hneedle == hhaystack and haystack[i..i+needle.length-1] == needle
hhaystack = Digest::MD5.hexdigest haystack[i+1..i+needle.length]
end
return -1
end
puts RabinKarp 'walter is fine' #=> fine
puts RabinKarp 'something in the way she moves' #=> he w
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment