Method: Containers::SuffixArray#has_substring?

Defined in:
lib/containers/suffix_array.rb

#has_substring?(substring) ⇒ Boolean Also known as: []

Returns true if the substring occurs in the string, false otherwise.

Complexity: O(m + log n)

s_array = Containers::SuffixArray.new("abracadabra")
s_array.has_substring?("a") #=> true
s_array.has_substring?("abra") #=> true
s_array.has_substring?("abracadabra") #=> true
s_array.has_substring?("acadabra") #=> true
s_array.has_substring?("adabra") #=> true
s_array.has_substring?("bra") #=> true
s_array.has_substring?("bracadabra") #=> true
s_array.has_substring?("cadabra") #=> true
s_array.has_substring?("dabra") #=> true
s_array.has_substring?("ra") #=> true
s_array.has_substring?("racadabra") #=> true
s_array.has_substring?("nope") #=> false

Returns:

  • (Boolean) 


51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
 
# File 'lib/containers/suffix_array.rb', line 51

def has_substring?(substring)
  substring = substring.to_s
  return false if substring.empty?
  substring_length = substring.length-1
  l, r = 0, @suffixes.size-1
  while(l <= r)
    mid = (l + r) / 2
    suffix = @suffixes[mid][0..substring_length]
    case substring <=> suffix
    when 0 then return true
    when 1 then l = mid + 1
    when -1 then r = mid - 1
    end
  end
  return false
end