class SuffixArray

Public Class Methods

new(suffixes) click to toggle source
Calls superclass method
# File lib/adlint/prelude.rb, line 269
def initialize(suffixes)
  super(suffixes.sort.map { |suffix| [suffix, 0] })
  update_height_of_each_suffixes!
end

Public Instance Methods

longest_common_prefix_length() click to toggle source
# File lib/adlint/prelude.rb, line 284
def longest_common_prefix_length
  self.map { |suffix, height| height }.max
end
longest_common_substrings() click to toggle source
# File lib/adlint/prelude.rb, line 274
def longest_common_substrings
  len = self.longest_common_prefix_length

  return [] if len == 0

  self.each_index.reduce([]) { |result, idx|
    self[idx][1] == len ? result + create_substring_pairs(idx, len) : result
  }
end

Private Instance Methods

create_substring_pairs(idx, len) click to toggle source
# File lib/adlint/prelude.rb, line 295
def create_substring_pairs(idx, len)
  base_suffix = self[idx][0]

  if base_suffix.lhs?
    create_entry = lambda { |lhs, rhs, l| SubstringPair.new(lhs, rhs, l) }
  else
    create_entry = lambda { |rhs, lhs, l| SubstringPair.new(lhs, rhs, l) }
  end

  result = []

  (0...idx).reverse_each do |i|
    break unless self[i + 1][1] == len

    unless base_suffix.same_owner?(self[i][0])
      result.push(create_entry[base_suffix, self[i][0], len])
    end
  end

  result
end
update_height_of_each_suffixes!() click to toggle source
# File lib/adlint/prelude.rb, line 289
def update_height_of_each_suffixes!
  (1...self.size).each do |idx|
    self[idx][1] = self[idx - 1][0].common_prefix_length(self[idx][0])
  end
end