Skip to content

Instantly share code, notes, and snippets.

@vincentchu
Created February 12, 2012 04:46
Show Gist options
  • Save vincentchu/1806413 to your computer and use it in GitHub Desktop.
Save vincentchu/1806413 to your computer and use it in GitHub Desktop.
Boyer Moore implemented in Ruby
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
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment