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