Skip to content

Instantly share code, notes, and snippets.

@danielrsmith

danielrsmith/test.rb Secret

Last active August 29, 2015 14:04
Show Gist options
  • Star 0 You must be signed in to star a gist
  • Fork 0 You must be signed in to fork a gist
  • Save danielrsmith/836c0fd602f7ebcf6be6 to your computer and use it in GitHub Desktop.
Save danielrsmith/836c0fd602f7ebcf6be6 to your computer and use it in GitHub Desktop.
Download ZIP
Raw
test.rb
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