module BoyerMoore

ported directly from this version wikipedia: en.wikipedia.org/w/index.php?title=Boyer%E2%80%93Moore_string_search_algorithm&diff=391986850&oldid=391398281 it's not very rubyish but it works

Public Class Methods

compute_prefix(str) click to toggle source
# File lib/boyermoore.rb, line 36
def self.compute_prefix(str)
  size = str.length
  k = 0
  result = [0]
  1.upto(size - 1) do |q|
    while (k > 0) && (str[k] != str[q])
      k = result[k-1]
    end
    k += 1 if(str[k] == str[q])
    result[q] = k
  end
  result
end
needle_matches?(needle, haystack) click to toggle source
# File lib/boyermoore.rb, line 110
def self.needle_matches?(needle, haystack)
  if needle.kind_of?(Regexp)
    needle.match(haystack) ? true : false
  else
    needle == haystack
  end
end
prepare_badcharacter_heuristic(str) click to toggle source
# File lib/boyermoore.rb, line 50
def self.prepare_badcharacter_heuristic(str)
  result = RichHash.new
  0.upto(str.length - 1) do |i|
    result[str[i]] = i
  end
  result
end
prepare_goodsuffix_heuristic(normal) click to toggle source
# File lib/boyermoore.rb, line 58
def self.prepare_goodsuffix_heuristic(normal)
  size = normal.size
  result = []

  reversed = normal.dup.reverse
  prefix_normal = compute_prefix(normal)
  prefix_reversed = compute_prefix(reversed)

  0.upto(size) do |i|
    result[i] = size - prefix_normal[size-1]
  end

  0.upto(size-1) do |i|
    j = size - prefix_reversed[i]
    k = i - prefix_reversed[i]+1
    result[j] = k if result[j] > k
  end
  result
end