комбинации подстрок в строке

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"]

Я не уверен, что вы ищете здесь дубликаты или нет. Вы можете столкнуться с сложной вычислительной проблемой, если не будете осторожны, поскольку именно такие вещи делают секвенирование ДНК чрезвычайно сложным.

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"].