Pattern Matching on Sparse Suffix Trees
2011Vol. 3887, pp. 92–97
Citations Over TimeTop 13% of 2011 papers
Abstract
We consider a compact text index based on evenly spaced sparse suffix trees of a text [9]. Such a tree is defined by partitioning the text into blocks of equal size and constructing the suffix tree only for those suffixes that start at block boundaries. We propose a new pattern matching algorithm on this structure. The algorithm is based on a notion of suffix links different from that of [9] and on the packing of several letters into one computer word.
Related Papers
- → Compressed Suffix Trees with Full Functionality(2007)294 cited
- → A time and space efficient data structure for string searching on large texts(1996)27 cited
- Linear-Time Search in Suffix Arrays(2005)
- Time and Space Efficient Search with Suffix Arrays(2005)
- → Suffix Trays and Suffix Trists: Structures for Faster Text Indexing(2014)