Suffix tree: Difference between revisions
Content added Content deleted
(Created page with "{{draft task}} A wp:suffix tree is a data structure commonly used in wp:string algorithms. Basically, for any string, its suffix tree is a wp:rooted tree where...") |
m (→{{header|Perl 6}}: minor style rewrite) |
||
Line 11: | Line 11: | ||
<lang Perl 6>sub suffixes(Str $str) { map &flip, [\~] $str.flip.comb } |
<lang Perl 6>sub suffixes(Str $str) { map &flip, [\~] $str.flip.comb } |
||
sub suffix-tree(@a) { |
sub suffix-tree(@a) { |
||
hash |
|||
@a == 0 ?? [] !! |
|||
@a == |
@a == 0 ?? () !! |
||
@a == 1 ?? @a[0] => [] !! |
|||
gather for @a.classify(*.substr(0, 1)) { |
|||
my $subtree = suffix-tree(grep *.chars, map *.substr(1), .value[]); |
my $subtree = suffix-tree(grep *.chars, map *.substr(1), .value[]); |
||
if $subtree.elems == 1 { |
if $subtree.elems == 1 { |
Revision as of 20:08, 10 May 2013
Suffix tree is a draft programming task. It is not yet considered ready to be promoted as a complete task, for reasons that should be found in its talk page.
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 "rosettacode$", and show that its edges are:
$ $ acode$ acode$ code$ de$ de$ e o rosettacode$ settacode$ settacode$ t tacode$ ttacode$
Perl 6
<lang Perl 6>sub suffixes(Str $str) { map &flip, [\~] $str.flip.comb } sub 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.elems == 1 { my $pair = $subtree.pick; take .key ~ $pair.key => $pair.value; } else { take .key => $subtree; } }
}
sub edges($tree) {
gather for $tree[] { take .key; .take for edges .value; } if $tree;
}
say sort edges suffix-tree suffixes 'rosettacode$';</lang>
Output matches the one in the task description.