Tìm chuỗi thường gặp trong mảng các chuỗi (ruby)

Question

Với tôi có một mảng của 3 chuỗi:

["Extra tv in bedroom", 
"Extra tv in living room", 
"Extra tv outside the shop"] 

Làm thế nào để tìm ra chuỗi dài nhất tất cả các chuỗi có điểm chung?

Answer 1

Đây là một cách rubyish làm nó. Bạn nên sử dụng thuật toán nâng cao hơn nếu bạn có một chuỗi các chuỗi hoặc chúng rất dài, mặc dù:

def longest_common_substr(strings) 
    shortest = strings.min_by &:length 
    maxlen = shortest.length 
    maxlen.downto(0) do |len| 
    0.upto(maxlen - len) do |start| 
     substr = shortest[start,len] 
     return substr if strings.all?{|str| str.include? substr } 
    end 
    end 
end 

puts longest_common_substr(["Extra tv in bedroom", 
          "Extra tv in living room", 
          "Extra tv outside the shop"]) 

Answer 2

This wikipedia article giải thích hai thuật toán có thể được sử dụng để giải quyết vấn đề đó.

Answer 3

Nếu bạn muốn tìm kiếm cho sự khởi đầu của tất cả các chuỗi:

Nguồn

def substr(a) 
    return "" unless (a.length > 0) 
    result = 0 
    (0 ... a.first.length).each do |k| 
     all_matched = true 
     character = a.first[k] 
     a.each{ |str| all_matched &= (character == str[k]) } 
     break unless all_matched 
     result+=1 
    end 
    a.first.slice(0,result) 
end 

thử nghiệm

input = ["Extra tv in bedroom", 
"Extra tv in living room", 
"Extra tv outside the shop"] 

puts substr(input) + "." 

Output

Extra tv . 

Answer 4

Đừng nghĩ rằng điều này đặc biệt tốt.

def longest_substr(text) 
    if (text.length == 0) 
     return "" 
    elseIf (text.length == 1) 
     return text[0] 
    end 
    longest = text.inject(text[0].length) {|min, s| min < s.length ? min : s.length} 
    (1 .. longest).to_a.reverse.each do |l| 
     (0 .. text[0].length - l).each do |offset| 
      str = text[0].slice(offset, l) 
      matched = (1 .. text.length - 1).inject(true) {|matched, i| matched && text[i].index(str) != nil} 
      if (matched) 
       return str 
      end 
     end 
    end 

    return "" 
end 

puts longest_substr(["Alice's Extra tv in bedroom", 
    "Bob's Extra tv in living room", 
    "My Extra tv outside the shop"]) 

Answer 5

Cũng chỉ cho đầu chuỗi.

def longest_subsequence array 
    array.sort! 
    first = array[0].split(//) 
    last = array[-1].split(//) 
    length = (first.size > last.size) ? last.size : first.size 
    sequence = "" 
    index = 0 
    while (first[index] == last[index]) && (index < length) 
    sequence << first[index] 
    index += 1 
    end 
    sequence 
end 

Nhưng tôi nghĩ phải có cách dễ dàng so sánh đầu chỉ hai chuỗi cho chuỗi con phù hợp - Tôi không thể nghĩ về nó ngay bây giờ!

Answer 6

Không biết liệu phản hồi có hữu ích hay không, nhưng đây là giải pháp lấy cảm hứng từ mã @mckeed và @ lins314159.

def longest_common_substr(strings) 
    longest_substring = strings.map{|s| s.split}.max_by &:length 
    longest_substring.inject do |target_str, token| 
     r = Regexp.new("^#{target_str.nil? ? token : "#{target_str} #{token}".strip}") 
     target_str = "#{target_str} #{token}".strip if strings.all? {|string| string =~ r} 
     target_str 
    end 
end 

puts longest_common_substr(["Extra tv and mat in bedroom", 
          "Extra tv and chair with view in living room", 
          "Extra tv and carpet outside the shop"])