在一组字符串中找到最长的公共起始子字符串[关闭]

Question

提出一个最优雅的JavaScript，Ruby或其他解决方案来解决一个相对琐碎的问题是一个挑战。

这个问题是Longest common
substring问题的
一个更具体的情况。我只需要找到数组中最长的公共
起始 子串。这大大简化了问题。

例如，最长的子字符串[interspecies, interstelar, interstate]是“ inters”。但是，我不需要在中找到“有意义”
[specifics, terrific]。

我已经通过用JavaScript快速编写一个解决方案来解决该问题，这是我对类似于shell的制表符补全（此处为测试页）的回答的一部分。这是稍作调整的解决方案：

function common_substring(data) {
  var i, ch, memo, idx = 0
  do {
    memo = null
    for (i=0; i < data.length; i++) {
      ch = data[i].charAt(idx)
      if (!ch) break
      if (!memo) memo = ch
      else if (ch != memo) break
    }
  } while (i == data.length && idx < data.length && ++idx)

  return (data[0] || '').slice(0, idx)
}

此代码可在Gist中获得，并且在Ruby中可以使用类似的解决方案。您可以将要点克隆为git
repo进行尝试：

$ git clone git://gist.github.com/257891.git substring-challenge

我对这些解决方案不是很满意。我觉得可以用更多的优雅和更少的执行复杂性来解决它们，这就是我要发布此挑战的原因。

我将接受我认为最优雅或最简洁的解决方案作为答案。例如，这是我想出的一个疯狂的Ruby黑客-&在String上定义运算符：

# works with Ruby 1.8.7 and above
class String
  def &(other)
    difference = other.to_str.each_char.with_index.find { |ch, idx|
      self[idx].nil? or ch != self[idx].chr
    }
    difference ? self[0, difference.last] : self
  end
end

class Array
  def common_substring
    self.inject(nil) { |memo, str| memo.nil? ? str : memo & str }.to_s
  end
end

首选使用JavaScript或Ruby的解决方案，但是只要您解释发生了什么，您就可以展示其他语言的巧妙解决方案。请仅从标准库中获取代码。

更新：我最喜欢的解决方案

我选择了JavaScript的分拣解决方案通过肯纳贝克为“答案”，因为它让我觉得既意外和天才。如果我们不考虑实际排序的复杂性（让我们想象一下它已被语言实现无限优化），则解决方案的复杂性就是比较两个字符串。

感谢您的参与！从评论中可以看到，我学到了很多东西（甚至是关于Ruby的知识）。

Answer 1

这是一个问题，但这是一个简单的javascript版本：它对数组进行排序，然后仅查看第一个和最后一个项目。

//数组中最长的公共起始子字符串

function sharedStart(array){
    var A= array.concat().sort(), 
    a1= A[0], a2= A[A.length-1], L= a1.length, i= 0;
    while(i<L && a1.charAt(i)=== a2.charAt(i)) i++;
    return a1.substring(0, i);
}

德莫斯

sharedStart(['interspecies', 'interstelar', 'interstate'])  //=> 'inters'
sharedStart(['throne', 'throne'])                           //=> 'throne'
sharedStart(['throne', 'dungeon'])                          //=> ''
sharedStart(['cheese'])                                     //=> 'cheese'
sharedStart([])                                             //=> ''
sharedStart(['prefix', 'suffix'])                           //=> ''