Boyer Moore implemented in Ruby

boyer_moore.rb

class BoyerMoore
  attr_accessor :text
  attr_reader :pattern, :matches

  def initialize( opts )
    @text = opts[:text]
  end

  def search( pattern_str )
    @pattern = Pattern.new( pattern_str )
    @matches = []
    shift    = pattern.length - 1

    while (shift < text.length)

      mismatch_pos, mismatch_char = check_text(shift)

      if (mismatch_pos == -1)
        @matches << shift
        shift += pattern.length
      else
        shift += pattern.shift_by(mismatch_char, mismatch_pos)
      end
    end
  end

  def print_matches(context = 10)
    matches.each do |match_pos|
      match_beg = match_pos - pattern.length + 1
      match_end = match_pos

      match_beg = [0, (match_beg-context)].max
      match_end = [(text.length-1), (match_end+context)].min

      match_text = text[match_beg..match_end]
      match_text.gsub!(pattern.pattern, "\x1b[31;1m#{pattern.pattern}\x1b[0m")
      puts "...#{match_text}..."
    end
  end

  private

  def check_text(shift)
    k     = 0
    p_len = pattern.length - 1

    while (pattern.pattern[p_len-k] == text[shift-k])
      k += 1

      break if (p_len < k)
    end

    if (p_len < k)
      return [-1, nil]
    else
      return [(p_len-k), text[(shift-k)..(shift-k)]]
    end
  end

  class Pattern

    attr_reader :chars, :length, :pattern

    def initialize(pattern)
      @pattern = pattern
      @length  = @pattern.length
      @chars   = {}

      pattern.split(//).each_with_index { |char, pos|
        @chars[char] ||= []
        @chars[char] << pos
      }
    end

    def shift_by(badchar, pos)
      [bad_char_shift(badchar, pos), good_suffix_shift(pos)].max
    end

    def bad_char_shift(badchar, pos)
      pattern_pos = (chars[badchar] || [0]).max

      (pos - pattern_pos)
    end

    def good_suffix_shift(pos)
      good_suffix = pattern[(pos+1)..(length-1)]

      max = 0
      (0..(pos-1)).each do |k|
        max = k if pattern[0..k].end_with?(good_suffix)
      end


      (length - max - 1)
    end
  end
end