123456789101112131415161718192021222324252627282930313233343536373839404142434445464748 |
- #!/usr/bin/ruby
- #
- ## https://rosettacode.org/wiki/Suffix_tree
- #
- func suffix_tree(Str t) {
- suffix_tree(^t.len -> map { t.substr(_) })
- }
- func suffix_tree({.is_empty}) { Hash() }
- func suffix_tree(a {.len == 1}) { Hash(a[0] => Hash()) }
- func suffix_tree(Arr a) {
- var h = Hash()
- for k,v in (a.group_by { .char(0) }) {
- var subtree = suffix_tree(v.map { .substr(1) })
- var subkeys = subtree.keys
- if (subkeys.len == 1) {
- var subk = subkeys[0]
- h{k + subk} = subtree{subk}
- }
- else {
- h{k} = subtree
- }
- }
- return h
- }
- var tree = suffix_tree('banana$')
- say tree
- assert_eq(tree, Hash(
- "$" => Hash(),
- "a" => Hash(
- "$" => Hash(),
- "na" => Hash(
- "$" => Hash(),
- "na$" => Hash()
- )
- ),
- "banana$" => Hash(),
- "na" => Hash(
- "$" => Hash(),
- "na$" => Hash()
- )
- ))
|