Suffix Tree
What is Suffix Tree ?
- First introduced by Weiner (1973), which Donald Knuth subsequently characterized as “Algorithm of the Year 1973”.
- The construction was greatly simplified by McCreight (1976) , and also by Ukkonen (1995).
- A Suffix Tree for a given text is a compressed trie for all suffixes of the given text.
Why Suffix Tree ?
- Helps to search pattern pat[0..m-1] in a text txt[0…n-1] where m < n.
- We have different algorithms like KMP Algorithm, Rabin-Karp Algorithm, Finite Automata based Algorithm and Boyer Moore Algorithm for doing the same task.
- All of the above algorithms preprocess the pattern to make the pattern searching faster.
- The best time complexity that we could get by preprocessing pattern is O(n) where n is length of the text.
- But in case of suffix trees, once the suffix tree is built after the preprocessing, we can search any pattern in O(m) time where m is length of the pattern.
- Preprocessing of text may become costly if the text changes frequently, so it is good for fixed text or less frequently changing text though.
Abstract Steps to Build a Suffix Tree?
- Generate all suffixes of given text.
- Consider all suffixes as individual words and build a compressed trie.
Abstract Steps to Search in Suffix Tree
- 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.
- 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 of Suffix Tree
Suffix tree can be used for a wide range of problems. Some famous problems where it provides optimal time complexity solution are:
- Pattern Searching
- Finding the longest repeated substring
- Finding the longest common substring
- Finding the longest palindrome in a string