Sampled Longest Common Prefix Array
arXiv:1001.2101 · doi:10.1007/978-3-642-13509-5_21
Abstract
When augmented with the longest common prefix (LCP) array and some other structures, the suffix array can solve many string processing problems in optimal time and space. A compressed representation of the LCP array is also one of the main building blocks in many compressed suffix tree proposals. In this paper, we describe a new compressed LCP representation: the sampled LCP array. We show that when used with a compressed suffix array (CSA), the sampled LCP array often offers better time/space trade-offs than the existing alternatives. We also show how to construct the compressed representations of the LCP array directly from a CSA.
arXiv commentThis is a slightly extended version of the paper that was presented at CPM 2010. The implementation is available at http://www.cs.helsinki.fi/group/suds/rlcsa/