Sampled longest common prefix array

Show full item record

Permalink

http://hdl.handle.net/10138/23555

Citation

Sirén , J 2010 , ' Sampled longest common prefix array ' in Combinatorial Pattern Matching : 21st Annual Symposium, CPM 2010 , pp. 227-237 Lecture Notes in Computer Science , no. 6129 . DOI: 10.1007/978-3-642-13509-5_21

Title: Sampled longest common prefix array
Author: Sirén, Jouni
Contributor: University of Helsinki, Department of Computer Science
Belongs to series: Lecture Notes in Computer Science
Belongs to series: Combinatorial Pattern Matching 21st Annual Symposium, CPM 2010
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
Peer review status: Peer reviewed
URI: http://hdl.handle.net/10138/23555
Date: 2010
Subject: 113 Computer and information sciences
Rights:


Files in this item

Total number of downloads: Loading...

Files Size Format View
paper.pdf 311.0Kb PDF View/Open

This item appears in the following Collection(s)

Show full item record