arrays - 确定数组/字符串中最大匹配序列的有效方法(在 Ruby 中)？

Question

假设我有两个单词数组:

array1 = ["hello", "world", "i", "am", "in", "the", "world"]
array2 = ["This", "is", "the", "hello", "world", "message"]

可以很容易地用两个字符串表示:

string1 = "hello world i am in the world"
string2 = "This is the hello world message"

假设我现在要使用数组。

我想找到 array2 的最大子数组，它在 array1 中以相同的顺序出现。

所以，如果你打算以可以想象到的最慢的方式去做，比如说，你会说:

• 从 array2 中获取所有 6 字子数组(其中有一个)。
  • 它是否按顺序出现在 array1 中？否
• 从 array2 中获取所有 5 字子数组(其中有两个)。
  • 它们中的任何一个出现在 array1 中的顺序是什么？否
• 从 array2 中获取所有的 4 字子数组。
  • 它们中的任何一个出现在 array1 中的顺序是什么？否
• 等等，直到我们到达
• 从 array2 中获取所有的 2-word 子数组。
  • 它们中的任何一个出现在 array1 中的顺序是什么？是的:["hello", "world"] 会。停止。

但是，这感觉效率很低。谁能看到更好的方法？我正在使用 Ruby，但我对通用算法以及如何使用该特定语言进行操作感兴趣。

请注意，这不仅仅是数组交集，因为它(至少在 ruby​​ 中)不关心元素的顺序，而我确实关心这一点。

谢谢!

Answer 1

这是一个快速有效的解决方案，减少了对数组中共有元素的比较:

array1 = ["hello", "world", "i", "am", "in", "the", "world"]
array2 = ["This", "is", "the", "hello", "world", "message"]

common_words = array1 & array2

stringified_array1 = array1.join(' ')
stringified_array2 = array2.join(' ')

(common_words.length - 1).downto(0).map do |n|
  stringified_combo = array1[0..n].join(' ')

  if stringified_array1.include?(stringified_combo) && stringified_array2.include?(stringified_combo)
    stringified_combo.split($,)
  end 
end.compact.max

这样你就得到了两个数组之间的共同词，并从大到小测试这些词。您检查它们在第一个数组中的顺序，然后检查它们是否存在于第二个数组中。

我相信这是有效的，尽管很高兴收到任何评论和反馈，