Sampled Longest Common Prefix Array

Details Sampled Longest Common Prefix Array Sampled Longest Common Prefix Array

2010-01-13

arxiv.org/abs/1001.2101v3

Computer Science

Data Structures and Algorithms

This is a slightly extended version of the paper that was presented at CPM 2010. The implementation is available at http://w

Scientific paper

10.1007/978-3-642-13509-5_21

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.

Affiliated with

Also associated with

No associations

Rating

Sampled Longest Common Prefix Array does not yet have a rating. At this time, there are no reviews or comments for this scientific paper.

If you have personal experience with Sampled Longest Common Prefix Array, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Sampled Longest Common Prefix Array will most certainly appreciate the feedback.

Rate now

Comments { 0 }

Profile ID: LFWR-SCP-O-524994