| Space Efficient Suffix Trees (2001) | |||||||||||||||||
Abstract | |||||||||||||||||
| We give the first representation of a suffix tree that uses n lg n+O(n) bits of space and supports searching for a pattern string in the given text (from a fixed size alphabet)in O(m) time, where n is the size of the text and m is the length of the pattern. The structure is quite simple and answers a question raised by Muthukrishnan in [22] | |||||||||||||||||
Publication details | |||||||||||||||||
| |||||||||||||||||