Data Structure - Suffix Tree
Suffix Tree is a compressed trie containing all
the suffixes of the given text T as their keys and positions in the text as their values.
Suffix tree of the text T can be built in the time linear to the length of T.
See algorithms of Ukkonen or
Example of the Suffix Tree built using Ukkonen's algorithm from a word "BANANA".
Suffix tree can be used to efficiently perform the following operations:
- Find all occurrences of a string P (pattern) in a text T
- Finding the longest common substring
Suffix tree is closely related to the following data structures:
The code can be tested on Ideone platform.
The input text is transformed to the DOT notation and can be rendered using Webgraphviz