Lightweight LCP-Array Construction in Linear Time

Details Lightweight LCP-Array Construction in Linear Time Lightweight LCP-Array Construction in Linear Time

2010-12-20

arxiv.org/abs/1012.4263v1

Computer Science

Data Structures and Algorithms

Scientific paper

The suffix tree is a very important data structure in string processing, but it suffers from a huge space consumption. In large-scale applications, compressed suffix trees (CSTs) are therefore used instead. A CST consists of three (compressed) components: the suffix array, the LCP-array, and data structures for simulating navigational operations on the suffix tree. The LCP-array stores the lengths of the longest common prefixes of lexicographically adjacent suffixes, and it can be computed in linear time. In this paper, we present new LCP-array construction algorithms that are fast and very space efficient. In practice, our algorithms outperform the currently best algorithms.

Affiliated with

Also associated with

No associations

Rating

Lightweight LCP-Array Construction in Linear Time 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 Lightweight LCP-Array Construction in Linear Time, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Lightweight LCP-Array Construction in Linear Time will most certainly appreciate the feedback.

Rate now

Comments { 0 }

Profile ID: LFWR-SCP-O-452992