Suffix Trees

Suffix tree for a string S is obtained by the following operations:

1. Find all the suffixes of the string and put in String [] ‘suffixes’

2. Sort the array ‘suffixes’. (This is just to make the creation of trie easier)

3. Create a trie for those suffixes.

4. Collapse those nodes in the trie to a single node which have single child only.

Example: If string was ‘peeper’, then its substrings are:

1. peeper

2. eeper

3. eper

4. per

5. er

6. r

Sorting the above gives:

1. eeper

2. eper

3. er

4. peeper

5. per

6. r

Trie for the above can be made as:

Now, if we collapse the nodes which have only one child, then this becomes as:

With the above suffix tree, it becomes very easy to find a substring.

We just check every child of root and then take a branch.

So, maximum worst case comparisons required here are |pat| rather than |S| where |pat| means length of the pattern to be searched and |S| means the length of the text whose suffix tree we have made.

To visualize a suffix tree, think that each of its branch helps us to traverse common sections of string S in one go. So, one can say that all the suffixes that have any small portion in common, amalgamate together to form a common branch of the tree.

Time and Complexity of building a suffix tree:

It may appear that suffix tree requires a huge amount of memory and space but algorithms are available which can construct a suffix tree in O(n) time and O(n) space where n is the length of the input string.

So, suffix trees become very useful when the text in which searching has to be done is static and the no of searches is high. Example: search for occurrences of a word in bible.