rabin_karp_string_search.rb

# attempt to perform hash based string search
# http://en.wikipedia.org/wiki/Rabin–Karp_algorithm
class HashStringSearch
    def search(pattern, target)
        table = {}

        # loop through the target string, building position matches for the candidate
        for i in 0 .. target.size
            candidate = target[i .. i + pattern.size - 1]
            table[candidate] ||= []
            table[candidate] << i
        end

        table[pattern] || []
    end
end

require "test/unit"
class HashStringSearchTest < Test::Unit::TestCase
    def setup
        @hash_string_search = HashStringSearch.new
    end

    def test_search
        assert_search_equals("ABC", "ABDABEABC")
        assert_search_equals("BOOM!", "HELLO WORLD")
    end

    def test_multiple_search
        results = @hash_string_search.search("ABC", "ABCABDABC")
        assert_equal 2, results.size
        assert_equal [0, 6], results 
    end

    protected
   
    def assert_search_equals(pattern, target)
        assert_equal target.index(pattern), @hash_string_search.search(pattern, target).first
    end
end