문자열의 부분 문자열 조합

Question

주어진 문자열에서 가능한 모든 문자열 조합 조합을 찾는 방법은 무엇입니까?

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

이 당신에게 줄 것이다 :

이

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

Answer 1

거친 생각이 같은 수 있습니다 :

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

반환하는

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

당신에게 줄 것이다 : 당신이 당신의 대답에 ["ab","aab","ab","ba","bab"]이 왜

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

을하지 않습니다.