Руби Самая короткая суперструна

Question

Цель самой короткой общей проблемы суперструн состоит в том, чтобы найти кратчайшую возможную строку, которая содержит каждую строку в данном наборе в качестве подстрок. Я понимаю, что проблема в "NP complete". Но есть приближенные стратегии для этой проблемы. Например, короткие строки

ABRAC
ACADA
ADABR
DABRA
RACAD

Как реализовать кратчайшую общую проблему суперструн, чтобы вывод для приведенных выше строк был ABRACADABRA? Другой пример

Given

fegiach
bfgiak
hfdegi
iakhfd
fgiakhg

строкаbfgiakhfdegiach возможное решение длины 15.

Я хотел бы реализовать это в Ruby, хотя у меня нет углубленного изучения алгоритмов, хотя я работаю над его улучшением.

Наивная жадная реализация будет включать создание массива суффиксов для каждой подстроки

def suffix_tree(string)
  size = string.length
  suffixes = Array.new(size)
  size.times do |i|
    suffixes[i] = string.slice(i, size)
  end
  suffixes
end

#store the suffixes in a hash
#key is a fragment, value = suffixes
def hash_of_suffixes(fragments)
  suffixes_hash = Hash.new
  fragments.each do |frag|
    suffixes_hash["#{frag}"]= suffix_tree(frag)
  end
  suffixes_hash
end


fragments = ['ABRAC','ACADA','ADABR','DABRA','RACAD']
h = hash_of_suffixes(fragments)

#then search each fragment in all the suffix trees and return the number of 
#overlaps for each key

#store the results in graph??
#find possible ordering of the fragments

I would be grateful with some help.

Answer 1

Обратите внимание на комментарий, указывающий на проблемы с вашими примерами. Также обратите внимание, что если есть какой-то хитрый способ сделать это, я не знаю, что это такое. Я просто перебираю все перестановки, соединяю их вместе и нахожу самые короткие.

class ShortestSuperstring
  def initialize(*strings)
    self.strings = strings
  end

  def call
    @result ||= smoosh_many strings.permutation.min_by { |permutation| smoosh_many(permutation.dup).size }
  end

  private

  attr_accessor :strings

  def smoosh_many(permutation, current_word='')
    return current_word if permutation.empty?
    next_word = permutation.shift
    smoosh_many permutation, smoosh_two(current_word, next_word)
  end

  def smoosh_two(base, addition)
    return base if base.include? addition
    max_offset(base, addition).downto 0 do |offset|
      return base << addition[offset..-1] if addition.start_with? base[-offset, offset]
    end
  end

  def max_offset(string1, string2)
    min string1.size, string2.size
  end

  def min(n1, n2)
    n1 < n2 ? n1 : n2
  end
end

И набор тестов:

describe ShortestSuperstring do
  def self.ss(*strings, possible_results)
    example "#{strings.inspect} can come from superstrings #{possible_results.inspect}" do
      result = described_class.new(*strings).call
      strings.each { |string| result.should include string }
      possible_results.should include(result), "#{result.inspect} was not an expected superstring."
    end
  end

  ss '', ['']
  ss "a", "a", "a", ['a']
  ss "a", "b", %w[ab ba]
  ss 'ab', 'bc', ['abc']
  ss 'bc', 'ab', ['abc']
  ss 'abcd', 'ab', ['abcd']
  ss 'abcd', 'bc', ['abcd']
  ss 'abcd', 'cd', ['abcd']
  ss 'abcd', 'a', 'b', 'c', 'd', ['abcd']
  ss 'abcd', 'a', 'b', 'c', 'd', 'ab', 'cd', 'bcd', ['abcd']

  %w[ABRAC ACADA ADABR DABRA RACAD].permutation.each do |permutation|
    ss *permutation, %w[RACADABRAC ADABRACADA]
  end

  %w[fegiach bfgiak hfdegi iakhfd fgiakhg].permutation.each do |permutation|
    ss *permutation, %w[bfgiakhgiakhfdegifegiach
                        bfgiakhgfegiachiakhfdegi
                        iakhfdegibfgiakhgfegiach
                        iakhfdegibfgiakhgfegiach
                        fegiachiakhfdegibfgiakhg
                        fegiachbfgiakhgiakhfdegi
                        iakhfdegifegiachbfgiakhg]
  end
end