Suffix tree: Difference between revisions
(→{{header|Perl 6}}: making a multi) |
(adding extra credits) |
||
Line 7: | Line 7: | ||
<pre>$ $ $ $ a banana$ na na na$ na$</pre> |
<pre>$ $ $ $ a banana$ na na na$ na$</pre> |
||
Extra-credit: use the [[visualize a tree]] task in order to show the whole tree. |
|||
=={{header|Perl 6}}== |
=={{header|Perl 6}}== |
Revision as of 12:13, 27 May 2013
A suffix tree is a data structure commonly used in string algorithms. Basically, for any string, its suffix tree is a rooted tree where each edge is labelled, and where the concatenation of all the labels from the root to a leaf uniquely identifies a suffix of the string.
For this task, build the suffix tree of the string "banana$", and show that its edges are:
$ $ $ $ a banana$ na na na$ na$
Extra-credit: use the visualize a tree task in order to show the whole tree.
Perl 6
<lang Perl 6>multi suffix-tree(Str $str) { suffix-tree map &flip, [\~] $str.flip.comb } multi suffix-tree(@a) {
hash @a == 0 ?? () !! @a == 1 ?? @a[0] => [] !! gather for @a.classify(*.substr(0, 1)) { my $subtree = suffix-tree(grep *.chars, map *.substr(1), .value[]); if $subtree == 1 { my $pair = $subtree.pick; take .key ~ $pair.key => $pair.value; } else { take .key => $subtree; } }
}
sub edges($tree) {
gather for $tree[] { .take for .key, edges .value; }
}
say sort edges suffix-tree 'banana$';</lang>
Output matches the one in the task description.
Racket
See Suffix trees with Ukkonen’s algorithm by Danny Yoo for more information on how to use suffix trees in Racket.
<lang racket>
- lang racket
(require (planet dyoo/suffixtree)) (define tree (make-tree)) (tree-add! tree (string->label "rosettacode$")) (for ([i (in-naturals)]
[c (node-children (tree-root tree))]) (printf "~a: ~a\n" i (label->string (node-up-label c))))
</lang> Output: <lang racket> 0: $ 1: e 2: de$ 3: o 4: code$ 5: acode$ 6: t 7: settacode$ 8: rosettacode$ </lang>