Ukkonen's Linear Suffix Tree Construction (JavaScript Demo)

Input your own the text string in the textfield below and click generate.
Don't forget to put a unique ending character for the text (usually it's '#').

Show Every Split

Each node in the picture is represented by NODE_INDEX(SUFFIX_LINK, SUBSTRING, START_INDEX, END_INDEX) where:

• NODE_INDEX is an integer generated as new node is created.
• SUFFIX_LINK is an integer that tells the suffix link of the node.
• SUBSTRING is the string connecting the parent node to this node.
• START_INDEX and END_INDEX is the index of the substring in the text.

The JavaScript code skeleton is taken from http://www.csse.monash.edu.au/~lloyd/tildeAlgDS/Tree/Suffix/. You will find also the step-by-step explanation in creating Suffix Tree for text "mississipi" in that site.

You also can use these text for more understanding on how it works:

• MISSISSIPPI#
• ABRACADABRA#
• THEGREATALBANIANFUTURE#
• ASTALAVISTABABY#
• ABRABRABRABRA#
• ABABABABA#
• AAAAAAAAAAA#
• AAAAABAAAAA#
• AAAAABCDEAAAAA#

If you like this demo, you may also like to see Linear Suffix Array construction's demo by Juha Karkkainen and Peter Sanders.