public
Created

  • Download Gist
substring.js
JavaScript
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22
// 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']) //=> ''
substring.rb
Ruby
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42
# 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

Please sign in to comment on this gist.

Something went wrong with that request. Please try again.