class BoyerMoore::Needle

Public Class Methods

new(needle) click to toggle source
# File lib/boyer_moore.rb, line 18
def initialize(needle)
  needle.size > 0 or raise "Must pass needle with size > 0"
  @needle = needle
end

Private Class Methods

prefix(string) click to toggle source
# File lib/boyer_moore.rb, line 88
def self.prefix(string)
  k = 0
  (1...string.length).reduce([0]) do |prefix, q|
    while k > 0 && string[k] != string[q]
      k = prefix[k - 1]
    end
    string[k] == string[q] and k += 1
    prefix[q] = k
    prefix
  end
end

Public Instance Methods

match_or_skip_by(haystack, haystack_index) click to toggle source
# File lib/boyer_moore.rb, line 27
def match_or_skip_by(haystack, haystack_index)
  if mismatch_idx = mismatch_index(haystack, haystack_index)
    mismatch_char_index = character_index(haystack[haystack_index + mismatch_idx])
    skip_by(mismatch_char_index, mismatch_idx)
  end
end
size() click to toggle source
# File lib/boyer_moore.rb, line 23
def size
  @needle.size
end

Private Instance Methods

character_index(char) click to toggle source
# File lib/boyer_moore.rb, line 45
def character_index(char)
  character_indexes[char] || -1
end
character_indexes() click to toggle source
# File lib/boyer_moore.rb, line 62
def character_indexes
  @char_indexes ||=
    (0...@needle.length).reduce({}) do |hash, i|
      hash[@needle[i]] = i
      hash
    end
end
good_suffix(compare_index) click to toggle source
# File lib/boyer_moore.rb, line 49
def good_suffix(compare_index)
  good_suffixes[compare_index]
end
good_suffixes() click to toggle source
# File lib/boyer_moore.rb, line 70
def good_suffixes
  @good_suffixes ||=
    begin
      prefix_normal   = self.class.prefix(@needle)
      prefix_reversed = self.class.prefix(@needle.reverse)
      result = []
      (0..@needle.size).each do |i|
        result[i] = @needle.size - prefix_normal[@needle.size-1]
      end
      (0...@needle.size).each do |i|
        j = @needle.size - prefix_reversed[i]
        k = i - prefix_reversed[i] + 1
        result[j] > k and result[j] = k
      end
      result
    end
end
mismatch_index(haystack, haystack_index) click to toggle source
# File lib/boyer_moore.rb, line 36
def mismatch_index(haystack, haystack_index)
  compare_index = size - 1
  while @needle[compare_index] == haystack[haystack_index + compare_index]
    compare_index -= 1
    compare_index < 0 and return nil
  end
  compare_index
end
skip_by(mismatch_char_index, compare_index) click to toggle source
# File lib/boyer_moore.rb, line 53
def skip_by(mismatch_char_index, compare_index)
  suffix_index = good_suffix(compare_index + 1)
  if mismatch_char_index <= compare_index && (m = compare_index - mismatch_char_index) > suffix_index
    m
  else
    suffix_index
  end
end