Skip to content

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]
return -1
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