最长的公共前缀和数组后缀

获取两个数组的最长公共前缀（从原始索引0开始的子数组）和后缀（以原始索引-1结尾的子数组）的最佳方法是什么？ 例如，给定两个数组：

[:foo, 1, :foo, 0, nil, :bar, "baz", false] [:foo, 1, :foo, 0, true, :bar, false] 

这些数组的最长公共前缀是：

 [:foo, 1, :foo, 0] 

并且这些数组的最长公共后缀是：

 [false] 

当索引0 / -1处的元素在原始数组中不同时，公共前缀/后缀应该是空数组。

Answer 1

一种可能的方案：

 a1 = [:foo, 1, 0, nil, :bar, "baz", false] a2 = [:foo, 1, 0, true, :bar, false] a1.zip(a2).take_while { |x, y| x == y }.map(&:first) #=> [:foo, 1, 0] 

反转输入数组和输出数组会找到一个公共后缀：

 a1.reverse.zip(a2.reverse).take_while { |x, y| x == y }.map(&:first).reverse #=> [false] 

边缘情况： zip填充带有nil值的“参数”数组：

 a1 = [true, nil, nil] a2 = [true] a1.zip(a2).take_while { |x, y| x == y }.map(&:first) #=> [true, nil, nil] 

通过将初始数组截断为第二个数组的长度可以避免这种情况：

 a1[0...a2.size].zip(a2).take_while { |x, y| x == y }.map(&:first) 

Answer 2

另一种没有边缘情况的解

 a1 = [:foo, 1, 0, nil, :bar, "baz", false] a2 = [:foo, 1, 0, true, :bar, false] a1.take_while.with_index {|v,i| a2.size > i && v == a2[i] } 

编辑：提高性能

 class Array def common_prefix_with(other) other_size = other.size take_while.with_index {|v,i| other_size > i && v == other[i] } end end a1.common_prefix_with a2 

Answer 3

先生们，启动你的引擎吧！

方法测试

我测试了@stefan给出的第二种方法，@ BroiSatse提出的两种方法以及我提供的三种方法。

 class Array #for broiSatse2 def common_prefix_with(other) other_size = other.size take_while.with_index {|v,i| other_size > i && v == other[i] } end end class Cars def self.stefan(a1,a2) a1[0...a2.size].zip(a2).take_while { |x, y| x == y }.map(&:first) end def self.broiSatse1(a1,a2) a1.take_while.with_index {|v,i| a2.size > i && v == a2[i] } end def self.broiSatse2(a1,a2) a1.common_prefix_with(a2) end def self.cary1(a,b) a[0,b.size].take_while.with_index { |e,i| e == b[i] } end def self.cary2(a,b) any, arr = a.zip(b).chunk { |e,f| e==f }.first any ? arr.map(&:first) : [] end def self.cary3(a,b) a[0,(0..[a.size, b.size].min).max_by { |n| (a[0,n]==b[0,n]) ? n : -1 }] end end 

我没有包括@ 6ftDan给出的解决方案（不要与5’Dan或7’Dan混淆），因为它没有通过所有测试。

构建测试arrays

random_arrays(n)构造一对数组。 n是两者中较小者的大小。 较大的是n+1的大小。

 def random_arrays(n) m = rand(n) # make arrays the same for the first m elements a = Array.new(m,0) b = Array.new(m,0) if m < n # make the m+1 elements different a << 0 b << 1 # randomly assign 0s and 1a to the remaining elements (nm-1).times { a << rand(2); b << rand(2) } if m < n - 1 end # make arrays unequal in length (rand(2) == 0) ? a << 0 : b << 0 [a,b] end 

确认测试方法给出相同的结果

 N = 10000 #size of smaller of two input arrays methods = Cars.methods(false) # ensure are methods produce the same results and that # all deal with edge cases properly 20.times do |i| test = case i when 0 then [[0,1],[1,1]] when 1 then [[0],[]] when 1 then [[0,0,0],[0,0]] else random_arrays(N) end soln = Cars.send(methods.first, *test) methods[1..-1].each do |m| unless soln == Cars.send(m, *test) puts "#{m} has incorrect solution for #{test}" exit end end end puts "All methods yield the same answers\n" 

标杆

 require 'benchmark' I = 1000 #number of array pairs to test @arr = I.times.with_object([]) { |_,a| a << random_arrays(N) } #test arrays #test method m def testit(m) I.times { |i| Cars.send(m, *@arr[i]) } end Benchmark.bm(12) { |bm| methods.each { |m| bm.report(m) { testit(m) } } end 

结果

 All methods yield the same answers user system total real stefan 11.260000 0.050000 11.310000 ( 11.351626) broiSatse1 0.860000 0.000000 0.860000 ( 0.872256) broiSatse2 0.720000 0.010000 0.730000 ( 0.717797) cary1 0.680000 0.000000 0.680000 ( 0.684847) cary2 13.130000 0.040000 13.170000 ( 13.215581) cary3 51.840000 0.120000 51.960000 ( 52.188477) 

Answer 4

这适用于唯一的数组。

字首

 x = [:foo, 1, 0, nil, :bar, "baz", false] y = [:foo, 1, 0, true, :bar, false] (x & y).select.with_index {|item,index| x.index(item) == index} 

输出： => [:foo, 1, 0]

在Arrays for Affix上运行reverse

 (x.reverse & y.reverse).select.with_index {|item,index| x.reverse.index(item) == index} 

输出： => [false]

Answer 5

三种解决方案：野蛮（＃3，初始答案），更好（＃2，第一次编辑）和最佳（＃1，@ Stefan答案的变体，第二次编辑）。

 a = [:foo, 1, :foo, 0, nil, :bar, "baz", false] b = [:foo, 1, :foo, 0, true, "baz", false] c = [:foo,1,:goo] d = [:goo,1,:new] 

注意b与OP的示例略有不同。

除非下面另有说明，否则将通过反转数组，应用common_prefix然后反转结果来计算公共后缀。

＃1

Stefan的答案的变体，它解决了它的zip和map （并保留了将一个数组截断到另一个数组的最多长度的技术）：

 def common_prefix(a,b) a[0,b.size].take_while.with_index { |e,i| e == b[i] } end common_prefix(a,b) #=> [:foo, 1, :foo, 0] common_prefix(c,d) #=> [] 

＃2

 def common_prefix(a,b) any, arr = a.zip(b).chunk { |e,f| e==f }.first any ? arr.map(&:first) : [] end def common_suffix(a,b) any, arr = a[a.size-b.size..-1].zip(b).chunk { |e,f| e==f }.to_a.last any ? arr.map(&:first) : [] end common_prefix(a,b) #=> [:foo, 1, :foo, 0] # Nore: any, arr = a.zip(b).chunk { |e,f| e==f }.to_a # => [[true, [[:foo, :foo], [1, 1], [:foo, :foo], [0, 0]]], # [false, [[nil, true], [:bar, :baz], ["baz", false], [false, nil]]]] common_suffix(a,b) #=> ["baz", false] # Note: any, arr = a[a.size-b.size..-1].zip(b).chunk { |e,f| e==f }.to_a # => [[false, [[1, :foo], [:foo, 1], [0, :foo], [nil, 0], [:bar, true]]], # [true, [["baz", "baz"], [false, false]]]] 

当:first被发送到枚举器Enumerable＃chunk时 ，返回枚举器的第一个元素。 因此，它的效率应与使用Enumerable＃take_while相当 。

 common_prefix(c,d) #=> [] common_suffix(c,d) #=> [] 

＃3

 def common_prefix(a,b) a[0,(0..[a.size, b.size].min).max_by { |n| (a[0,n]==b[0,n]) ? n : -1 }] end common_prefix(a,b) #=> [:foo, 1, :foo, 0] common_prefix(c,d) #=> []