bm_string_search.rb

class BmStringSearch
  def initialize(target)
    @target = target
    @skip = {}
    i = target.size - 1
    target.each_char do |x|
      @skip[x] = i
      i -= 1
    end
  end

  def find_in(text)
    text_index = 0
    while text_index + @target.size - 1 < text.size
      target_last_index.downto(0) do |i|
        c = text[text_index + i]
        # puts "text_index:#{text_index}, i:#{i}, text:#{c}, target:#{@target[i]}"
        if @target[i] == c
          return text_index if i.zero?
        else
          text_index += skip_size(c).zero? ? 1 : skip_size(c)
          break
        end
      end
    end
  end

  private
  def target_last_index
    @target.size - 1
  end

  def skip_size(c)
    @skip[c] || @target.size
  end
end

if $0 == __FILE__
  require 'test/unit'

  class BmTest < Test::Unit::TestCase
    def setup
      @bmpattern = BmStringSearch.new('abcd')
    end

    def test
      assert_equal(0, @bmpattern.find_in('abcdefg'))
      assert_equal(6, @bmpattern.find_in('xxxabcabcdxxx'))
      assert_equal(10, @bmpattern.find_in('xxxcbcdxxxabcd'))
      assert_nil(@bmpattern.find_in('xxxabcabcaxxx'))

      chars = 'a'.upto('e').to_a
      0.upto(200).each do
        text = 0.upto(300).inject('') {|s, i| s << chars[Random.rand chars.size]}
        expected = text.index('abcd')
        got = @bmpattern.find_in(text)
        assert_equal(expected, got)
      end
    end
  end
end