sidef/scripts/RosettaCode/longest_common_prefix.sf

#!/usr/bin/ruby

#
## https://rosettacode.org/wiki/Longest_common_prefix
#

# Finds the first point where the tree bifurcates
func find_common_prefix(hash, acc) {
    if ((var keys = hash.keys).len == 1) {
        return __FUNC__(hash{keys[0]}, acc+keys[0])
    }
    return acc;
}

# Creates a tree like: {a => {b => {c => {}}}}
func lcp(*strings) {
    var hash = Hash()

    strings.sort_by{.len}.each { |str|
        var ref = hash
        str.is_empty && return ''
        str.each { |char|
            if (ref.has_key(char)) {
                ref = ref{char}
                ref.keys.len == 0 && break
            } else {
                ref = (ref{char} = Hash())
            }
        };
    };

    return find_common_prefix(hash, '')
}

var data = [
  ["interspecies","interstellar","interstate"],
  ["throne","throne"],
  ["throne","dungeon"],
  ["throne","","throne"],
  ["cheese"],
  [""],
  [],
  ["prefix","suffix"],
  ["foo","foobar"]
]

data.each { |set|
    say "lcp(#{set.dump.substr(1,-1)}) = #{lcp(set...).dump}"
}