Longest common prefix

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

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

    for str in (strings.sort_by{.len}) {
        var ref = hash
        str.is_empty && return ''
        for char in str {
            if (ref.contains(char)) {
                ref = ref{char}
                ref.len == 0 && break
            }
            else {
                ref = (ref{char} = Hash())
            }
        }
    }

    return find_common_prefix(hash, '')
}

Demonstration:

Output:

PreviousLong yearNextLongest common subsequence

Last updated

Was this helpful?