Sampled longest common prefix array

J Sirén - Annual Symposium on Combinatorial Pattern Matching, 2010 - Springer
Annual Symposium on Combinatorial Pattern Matching, 2010Springer
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 …
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.
Springer
以上显示的是最相近的搜索结果。 查看全部搜索结果