Suffix Tree

A Suffix Tree for a given text is a compressed trie for all suffixes of the given text.

How to build a Suffix Tree for a given text?

As discussed above, Suffix Tree is compressed trie of all suffixes, so following are very abstract steps to build a suffix tree from given text.

1. Generate all suffixes of given text.
2. Consider all suffixes as individual words and build a compressed trie.

How to search a pattern in the built suffix tree?

We have discussed above how to build a Suffix Tree which is needed as a pre-processing step in pattern searching. Following are abstract steps to search a pattern in the built Suffix Tree.

1. Starting from the first character of the pattern and root of Suffix Tree, do following for every character.
   • For the current character of pattern, if there is an edge from the current node of suffix tree, follow the edge.
   • If there is no edge, print “pattern doesn’t exist in text” and return.
2. If all characters of pattern have been processed, i.e., there is a path from root for characters of the given pattern, then print “Pattern found”.

Applications

1. Pattern Searching
2. Finding the longest repeated substring
3. Finding the longest common substring
4. Finding the longest palindrome in a string