Class Containers::SuffixArray

  1. lib/containers/suffix_array.rb
Parent: Object

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.

Methods

public class

  1. new

public instance

  1. []
  2. has_substring?

Public class methods

new (string)

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
[show source]
    # File lib/containers/suffix_array.rb, line 21
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

[] (substring)

Alias for has_substring?

has_substring? (substring)

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
[show source]
    # File lib/containers/suffix_array.rb, line 51
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