Sampled Longest Common Prefix Array
From MaRDI portal
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.
Recommendations
- Permuted Longest-Common-Prefix Array
- String inference from longest-common-prefix array
- String inference from longest-common-prefix array
- Computing the longest common prefix array based on the Burrows-Wheeler transform
- scientific article; zbMATH DE number 1786458
- Space-Time Tradeoffs for Longest-Common-Prefix Array Computation
- The colored longest common prefix array computed via sequential scans
- Computing Longest Common Substrings Via Suffix Arrays
- Longest common prefix with mismatches
Cited in
(10)- String inference from longest-common-prefix array
- String inference from longest-common-prefix array
- LCP array construction in external memory
- Longest common prefix with mismatches
- Permuted Longest-Common-Prefix Array
- Wee LCP
- Better external memory LCP array construction
- Tighter bounds for the sum of irreducible LCP values
- scientific article; zbMATH DE number 2119665 (Why is no real title available?)
- Tighter bounds for the sum of irreducible LCP values
This page was built for publication: Sampled Longest Common Prefix Array
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q3575250)
