-1

最短常见超字符串问题的目标是找到包含给定集合中的每个字符串作为子字符串的最短可能字符串。我知道问题是“NP完成”。但是有针对该问题的近似策略。例如，给定短字符串

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.
4

1 回答 1

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
于 2012-09-03T06:46:07.237 回答