title: Find the longest common starting substring in a set of strings
body: <p>This is a challenge to come up with the most elegant JavaScript, Ruby or other solution to a relatively trivial problem.</p>
  
  <p>This problem is a more specific case of the <a href="http://en.wikipedia.org/wiki/Longest_common_substring_problem" rel="nofollow noreferrer">Longest common substring problem</a>. I need to only find the longest common <strong>starting</strong> substring in an array. This greatly simplifies the problem.</p>
  
  <p>For example, the longest substring in <code>[interspecies, interstelar, interstate]</code> is "inters". However, I don't need to find "ific" in <code>[specifics, terrific]</code>.</p>
  
  <p>I've solved the problem by quickly coding up a solution in JavaScript as a part of my <a href="https://stackoverflow.com/questions/1837555/ajax-autocomplete-or-autosuggest-with-tab-completion-autofill-similar-to-shell/1897480#1897480">answer about shell-like tab-completion</a> (<a href="http://mislav.net/scripts/autocomplete.html" rel="nofollow noreferrer">test page here</a>). Here is that solution, slightly tweaked:</p>
  
  <pre><code>function common_substring(data) {
    var i, ch, memo, idx = 0
    do {
      memo = null
      for (i=0; i &lt; data.length; i++) {
        ch = data[i].charAt(idx)
        if (!ch) break
        if (!memo) memo = ch
        else if (ch != memo) break
      }
    } while (i == data.length &amp;&amp; idx &lt; data.length &amp;&amp; ++idx)
  
    return (data[0] || '').slice(0, idx)
  }
  </code></pre>
  
  <p>This <a href="http://gist.github.com/257891" rel="nofollow noreferrer">code is available in this Gist</a> along with a similar solution in Ruby. You can clone the gist as a git repo to try it out:</p>
  
  <pre><code>$ git clone git://gist.github.com/257891.git substring-challenge
  </code></pre>
  
  <p>I'm not very happy with those solutions. I have a feeling they might be solved with more elegance and less execution complexity—that's why I'm posting this challenge.</p>
  
  <p>I'm going to accept as an answer the solution I find the most elegant or concise. Here is for instance a crazy Ruby hack I come up with—defining the <code>&amp;</code> operator on String:</p>
  
  <pre><code># works with Ruby 1.8.7 and above
  class String
    def &amp;(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 &amp; str }.to_s
    end
  end
  </code></pre>
  
  <p>Solutions in JavaScript or Ruby are preferred, but you can show off clever solution in other languages as long as you explain what's going on. Only code from standard library please.</p>
  
  <h3>Update: my favorite solutions</h3>
  
  <p>I've chosen the <a href="/questions/1916218/find-the-longest-common-starting-substring-in-a-set-of-strings/1917041#1917041">JavaScript sorting solution</a> by <a href="https://stackoverflow.com/users/80860/kennebec">kennebec</a> as the "answer" because it struck me as both unexpected and genius. If we disregard the complexity of actual sorting (let's imagine it's infinitely optimized by the language implementation), the complexity of the solution is just comparing two strings.</p>
  
  <p>Other great solutions:</p>
  
  <ul>
  <li><a href="/questions/1916218/find-the-longest-common-starting-substring-in-a-set-of-strings/1922153#1922153">"regex greed"</a> by FM takes a minute or two to grasp, but then the elegance of it hits you. Yehuda Katz also made <a href="/questions/1916218/find-the-longest-common-starting-substring-in-a-set-of-strings/1916398#1916398">a regex solution</a>, but it's more complex</li>
  <li><a href="/questions/1916218/find-the-longest-common-starting-substring-in-a-set-of-strings/1916632#1916632"><code>commonprefix</code> in Python</a> — Roberto Bonvallet used a feature made for handling filesystem paths to solve this problem</li>
  <li><a href="/questions/1916218/find-the-longest-common-starting-substring-in-a-set-of-strings/1918438#1918438">Haskell one-liner</a> is short as if it were compressed, and beautiful</li>
  <li><a href="/questions/1916218/find-the-longest-common-starting-substring-in-a-set-of-strings/1916480#1916480">the straightforward Ruby one-liner</a></li>
  </ul>
  
  <p>Thanks for participating! As you can see from the comments, I learned a lot (even about Ruby).</p>