查找常見字符串中的字符串（紅寶石）的陣列

Question

鑑於我有3個字符串數組：

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

如何找到最長的字符串的所有字符串有什麼共同點？

Answer 1

這裏做的rubyish方式它。您應該使用更先進的算法，如果你有一大堆的字符串或者他們是很長，但：

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解釋了可用於解決該問題的兩種算法。

Answer 3

如果你要搜索的所有字符串的開頭：

來源

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 

測試

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

puts substr(input) + "." 

輸出

Extra tv . 

Answer 4

不要以爲這擴展特別好。

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

也只適用於字符串的開頭。

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 

但我認爲應該是一種能夠方便地比較只是兩個字符串的開始部分匹配的子 - 我只是想不出它現在！

Answer 6

不知道響應是否仍然有用，但這裏有一個解決方案，它受@mckeed和@ 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"])