Suffix Trees
Suffix tree for a string S is obtained by the following operations:
Example: If string was ‘peeper’, then its substrings are:
Sorting the above gives:
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.
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.
|
Got a thought to share or found a
bug in the code?
We'd love to hear from you:
Name: | |
Email: | (Your email is not shared with anybody) |
Comment: |
Facebook comments: