1234567891011121314151617181920212223242526272829303132333435363738394041424344454647484950 |
- #!/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}"
- }
|