字符串中子字符串的组合

Question

如何找到给定字符串中一组字符串的所有可能组合？

strings = ["ab","aa","ab","bb","ba","aba","aab"]
given_string = "abaababbab"

必须返回：

[
 ["ab","aa","ba","bb","ab],
 ["ab","aab","ab","ba","bab"]
 ["aba","aba","bb","ab"]
] 

Answer 1

一个粗略的想法可能是这样的：

strings.select do |s|
  given_string.index(s)
end

这会给你：

["ab", "aa", "ab", "bb", "ba", "aba", "aab"]

我不确定你是否在这里寻找重复项。如果你不小心的话，你可能会遇到计算复杂的问题，因为这类事情使得 DNA 测序变得异常计算密集。

Answer 2

以下：

strings = ["ab","aa","ab","bb","ba","aba","aab"]
@strings = strings.uniq!
@given_string = 'abaababbab'
@given_length = @given_string.length

def parse
  @parses.each do |parse|
    before = parse.pop # offset of the part that hasn't yet been parsed
    @strings.each do |str|
      next unless m = @given_string.match(str, before)
      first, last = m.offset(0)
      next unless first == before
      if last == @given_length
        @completed_parses.push([*parse, str])
      else
        @new_parses.push([*parse, str, last])
      end
    end
  end
  @parses = @new_parses
  @new_parses = []
  parse unless @parses.empty?
end

@parses = [[0]]
@new_parses = []
@completed_parses = []
parse
p @completed_parses

会给你：

[["aba", "aba", "bb", "ab"], ["ab", "aa", "ba", "bb", "ab"]]

我不明白为什么你的答案中有 ["ab","aab","ab","ba","bab"] 。