Suffix tree: Difference between revisions
Content deleted Content added
update task description. |
note about labels |
||
Line 14: | Line 14: | ||
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. |
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 labels should be encoded. Latitude is given in this matter. |
There are several ways to implement the tree data structure, for instance how edges labels should be encoded. 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 <math>O(n)</math>, but such an algorithm might be difficult to implement. An easier, <math>O(n^2)</math> algorithm is accepted. |
The computation time for an efficient algorithm should be <math>O(n)</math>, but such an algorithm might be difficult to implement. An easier, <math>O(n^2)</math> algorithm is accepted. |