Growing A Suffix Tree

CS251 "Data Structures and Algorithms" - applet #9 by Alexandru Edgar Ghitza (9630469) and Philippe-Antoine Warda (9632175).

This interactive Java applet allows the user to view the growth of the suffix tree of any given string he enters. This applet has many interesting properties. The nodes in green are the leaves of the suffix tree. As such, they include the index of the particular suffix they contain. This suffix is available by right-clicking on the leaf's node. That said, any string of length n will have n+1 suffixes as the $ is included in the analysis of the string by convention and is considered the (n+1)th suffix. The red colored nodes are, of course, the internal nodes of the tree. With the convention that "a" represents the beginning of a substring and "b" the end of this substring, the user will find that the pairs of indices, (a,b), indicate the label of each particular edge of the suffix tree. The string corresponding to this label can be viewed by left-clicking on the node. In order to do one insertion at a time and see the tree grow, press the NEXT button. If you only want to view the complete suffix tree of the string, click on the END button.

As an example, if you were to enter the string "GOOGOL" in the text field of the applet and click the ACCEPT bouton, you would notice that the complete suffix tree consists of 9 edges and 10 nodes (7 green leaves and 3 red internal nodes). The particular index 3 of the fifth leaf would, of course, indicate the suffix "OGOL$" and the label (4,7) would indicate the substring "GOL$". For further information concerning suffix trees and tries, may we recommend the following link : Topic #7: TRIES AND SUFFIX TREES.

And here is the source code.