Encontrar cadena común en matriz de cadenas (rubí)

Question

Dado que tengo una matriz de 3 cuerdas:

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

¿Cómo puedo encontrar la cadena más larga de todas las cadenas tienen en común?

Answer 1

Aquí está una manera rubyish de hacer eso. Debe utilizar un algoritmo más avanzado si usted tiene un montón de cuerdas o son muy largas, sin embargo:

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 explica dos algoritmos que se pueden utilizar para resolver ese problema.

Answer 3

Si desea buscar el principio de todas las cadenas:

Fuente

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 

prueba

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

puts substr(input) + "." 

salida

Extra tv . 

Answer 4

no creo que esto escalas particularmente bien.

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

También solo para el comienzo de las cadenas.

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 

Pero creo que debe haber una manera de comparar fácilmente el comienzo de sólo dos cuerdas de una subcadena coincidente - No puedo pensar en ello ahora mismo!

Answer 6

No sé si una respuesta todavía es útil, pero aquí hay una solución inspirada en el código de @mckeed y @ 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"])