Skip to content

Instantly share code, notes, and snippets.

@mislav
Created December 16, 2009 15:10
Show Gist options
  • Save mislav/257891 to your computer and use it in GitHub Desktop.
Save mislav/257891 to your computer and use it in GitHub Desktop.
// Finds the longest common starting substring in an array of strings
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)
}
common_substring(['interspecies', 'interstelar', 'interstate']) //=> 'inters'
common_substring(['throne', 'throne']) //=> 'throne'
common_substring(['throne', 'dungeon']) //=> ''
common_substring(['cheese']) //=> 'cheese'
common_substring([]) //=> ''
common_substring(['prefix', 'suffix']) //=> ''
# Finds the longest common starting substring in an array of strings
class Array
def common_substring
return self.first.to_s if self.length < 2
idx = 0
other = self.dup
base = other.shift
begin
ch = base[idx, 1]
match = self.all? { |str| str[idx, 1] == ch }
end while match and idx < base.length and (idx += 1)
base[0,idx]
end
end
if __FILE__ == $0
# in case this file is ran with `ruby -rubygems substring.rb`
# (needs `gem install rspec`)
require 'spec/autorun'
describe '#common_substring' do
def self.it(msg = nil, &block)
if msg and !block and msg =~ /extract '(.*?)' from \[(.*?)\]/
result, data = $1, $2.split(/\s*,\s*/)
super(msg) { data.common_substring.should == result }
else
super
end
end
it "should extract 'inters' from [interspecies, interstelar, interstate]"
it "should extract 'throne' from [throne, throne]"
it "should extract '' from [throne, dungeon]"
it "should extract 'cheese' from [cheese]"
it "should extract '' from []"
it "should extract '' from [prefix, suffix]"
end
end
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment