Sampled longest common prefix array
| Contribuinte(s) |
University of Helsinki, Department of Computer Science (-2009) |
|---|---|
| Data(s) |
2010
|
| Resumo |
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 |
| Formato |
11 |
| Identificador | |
| Idioma(s) |
eng |
| Relação |
Combinatorial Pattern Matching 21st Annual Symposium, CPM 2010 Lecture Notes in Computer Science |
| Fonte |
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 . , 10.1007/978-3-642-13509-5_21 |
| Palavras-Chave | #113 Computer and information sciences |
| Tipo |
A4 Article in conference publication (refereed) info:eu-repo/semantics/conferencePaper info:eu-repo/semantics/acceptedVersion |
