12345678910111213141516171819202122232425262728293031323334353637383940414243444546474849505152 |
- #!/usr/bin/ruby
- #
- ## https://rosettacode.org/wiki/Longest_common_prefix#Sidef
- #
- # 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, '')
- }
- 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}";
- }
|