user
A suffix tree is a data structure commonly used in string algorithms.

Given a string S of length n, its suffix tree is a tree T such that:

* T has exactly n leaves numbered from 1 to n.
* Except for the root, every internal node has at least two children.
* Each edge of T is labelled with a non-empty substring of S.
* No two edges starting out of a node can have string labels beginning with the same character.
* The string obtained by concatenating all the string labels found on the path from the root to leaf i spells out suffix S[i..n], for i from 1 to n.

Such a tree does not exist for all strings. To ensure existence, a character that is not found in S must be appended at its end. The character '$' is traditionally used for this purpose.

For this task, build and display the suffix tree of the string "banana$". Displaying the tree can be done using the code from the visualize a tree task, but any other convenient method is accepted.

There are several ways to implement the tree data structure, for instance how edges should be labelled. Latitude is given in this matter, but notice that a simple way to do it is to label each node with the label of the edge leading to it.

The computation time for an efficient algorithm should be 

O
(
n
)
{\displaystyle {\displaystyle O(n)}}
, but such an algorithm might be difficult to implement. An easier, 

O
(

n

2
)
{\displaystyle {\displaystyle O(n^{2})}}
 algorithm is accepted.
assistant
(formerly Perl 6)

**Works with**: Rakudo version 2018.04

Here is quite a naive algorithm, probably 

O
(

n

2
)
{\displaystyle {\displaystyle O(n^{2})}}
.

The display code is a variant of the visualize a tree task code.

```
multi suffix-tree(Str $str) { suffix-tree flat 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;
        }
    }
}

my $tree = root => suffix-tree 'banana$';

.say for visualize-tree $tree, *.key, *.value.List;

sub visualize-tree($tree, &label, &children,
                   :$indent = '',
                   :@mid = ('├─', '│ '),
                   :@end = ('└─', '  '),
) {
    sub visit($node, *@pre) {
        gather {
            take @pre[0] ~ $node.&label;
            my @children = sort $node.&children;
            my $end = @children.end;
            for @children.kv -> $_, $child {
                when $end { take visit($child, (@pre[1] X~ @end)) }
                default   { take visit($child, (@pre[1] X~ @mid)) }
            }
        }
    }
    flat visit($tree, $indent xx 2);
}

```

Output:

```
root
├─$
├─a
│ ├─$
│ └─na
│   ├─$
│   └─na$
├─banana$
└─na
  ├─$
  └─na$
```