Trovare stringa comune in array di stringhe (Ruby)

Question

Dato che ho un array di stringhe 3:

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

Come faccio a trovare la stringa più lunga tutte le stringhe hanno in comune?

Answer 1

Ecco un modo rubyish di fare esso. Si consiglia di utilizzare un algoritmo più avanzato se si dispone di un gruppo di stringhe o sono molto lunghi, però:

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 spiega due algoritmi che possono essere utilizzati per risolvere questo problema.

Answer 3

Se si desidera cercare l'inizio di tutte le stringhe:

Fonte

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 

prova

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

puts substr(input) + "." 

uscita

Extra tv . 

Answer 4

Non credo che questo scale particolarmente bene.

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

Anche solo per l'inizio di stringhe.

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 

Ma penso che ci dovrebbe essere un modo per confrontare facilmente l'inizio di soli due stringhe per una sottostringa di corrispondenza - non riesco proprio a pensare che in questo momento!

Answer 6

Non so se una risposta è ancora utile, ma ecco una soluzione ispirata al codice @mckeed e @ 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"])