class Containers::SuffixArray
A suffix array enables fast substring search of a given string. An array of all possible substrings is constructed and stored, and a binary search is then done to find a desired substring among those stored. While more storage (and thus memory) is needed to create the SuffixArray, the advantage is that substrings can be found in O(m log n) time, where m is the length of the substring to search for and n is the total number of substrings.
Public Class Methods
new(string)
click to toggle source
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 = Containers::SuffixArray("abracadabra") s_array["abra"] #=> true number = Containers::SuffixArray(1234567) number[1] #=> true number[13] #=> false
# File lib/containers/suffix_array.rb 21 def initialize(string) 22 string = string.to_s 23 raise ArgumentError, "SuffixArray needs to be initialized with a non-empty string" if string.empty? 24 @original_string = string 25 @suffixes = [] 26 string.length.times do |i| 27 @suffixes << string[i..-1] 28 end 29 30 # Sort the suffixes in ascending order 31 @suffixes.sort! { |x, y| x <=> y } 32 end
Public Instance Methods
has_substring?(substring)
click to toggle source
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
# File lib/containers/suffix_array.rb 51 def has_substring?(substring) 52 substring = substring.to_s 53 return false if substring.empty? 54 substring_length = substring.length-1 55 l, r = 0, @suffixes.size-1 56 while(l <= r) 57 mid = (l + r) / 2 58 suffix = @suffixes[mid][0..substring_length] 59 case substring <=> suffix 60 when 0 then return true 61 when 1 then l = mid + 1 62 when -1 then r = mid - 1 63 end 64 end 65 return false 66 end
Also aliased as: []