Class: Algorithms::Containers::SuffixArray

Inherits:
Object
  • Object
show all
Defined in:
lib/containers/suffix_array.rb

Instance Method Summary collapse

Constructor Details

#initialize(string) ⇒ SuffixArray

Creates a new SuffixArray with a given string. Object of any class implementing a #to_s method can be passed in, such as integers.

Complexity: O(n^2 log n)

s_array = Algorithms::Containers::SuffixArray.new("abracadabra")
s_array["abra"] #=> true

number = Algorithms::Containers::SuffixArray.new(1234567)
number[1] #=> true
number[13] #=> false

Raises:

  • (ArgumentError) 


23
24
25
26
27
28
29
30
31
32
33
34
 
# File 'lib/containers/suffix_array.rb', line 23

def initialize(string)
  string = string.to_s
  raise ArgumentError, "SuffixArray needs to be initialized with a non-empty string" if string.empty?
  @original_string = string
  @suffixes = []
  string.length.times do |i|
    @suffixes << string[i..-1]
  end

  # Sort the suffixes in ascending order
  @suffixes.sort! { |x, y| x <=> y }
end

Instance Method Details

#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 = Algorithms::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) 


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

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