Space-Time Tradeoffs for Longest-Common-Prefix Array Computation

DOI10.1007/978-3-540-92182-0_14MaRDI QIDQ3596712zbMATH OpenOpenAlexFDO

Authors Simon J. Puglisi, Andrew Turpin

Publication date 29 January 2009

Published in Algorithms and Computation (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1007/978-3-540-92182-0_14

Mathematics Subject Classification ID

Data structures (68P05) Algorithms on strings (68W32)

Recommendations

• Time-space trade-offs for longest common extensions
• Time-Space Trade-Offs for Longest Common Extensions
• scientific article; zbMATH DE number 1786458
• Practical Performance of Space Efficient Data Structures for Longest Common Extensions.
• Low space external memory construction of the succinct permuted longest common prefix array
• Towards a real time algorithm for parameterized longest common prefix computation
• Time-space trade-offs for the longest common substring problem
• Computing the longest common prefix array based on the Burrows-Wheeler transform
• I/O efficient dynamic data structures for longest prefix queries

Cited in

(28)

• Parameterized longest previous factor
• Faster online computation of the succinct longest previous factor array
• scientific article; zbMATH DE number 1786458 (Why is no real title available?)
• Practical compressed suffix trees
• LCP array construction using \(O(\operatorname{sort}(n))\) (or less) I/Os
• Low space external memory construction of the succinct permuted longest common prefix array
• Faster semi-external suffix sorting
• Variations of the parameterized longest previous factor
• Algorithm Theory - SWAT 2004
• LCP array construction in external memory
• Practical Performance of Space Efficient Data Structures for Longest Common Extensions.
• The colored longest common prefix array computed via sequential scans
• scientific article; zbMATH DE number 1945184 (Why is no real title available?)
• Computing regularities in strings: a survey
• Time-Space Trade-Offs for Longest Common Extensions
• Lightweight LCP construction for very large collections of strings
• Permuted Longest-Common-Prefix Array
• Sampled Longest Common Prefix Array
• Small-space LCE data structure with constant-time queries
• Better external memory LCP array construction
• Space-efficient construction of compressed suffix trees
• Fast, practical algorithms for computing all the repeats in a string
• scientific article; zbMATH DE number 2119665 (Why is no real title available?)
• Time-space trade-offs for longest common extensions
• Compressed communication complexity of longest common prefixes
• Longest common prefix arrays for succinct \(k\)-spectra
• Locally consistent parsing for text indexing in small space
• Space-time trade-offs for the LCP array of Wheeler DFAs

This page was built for publication: Space-Time Tradeoffs for Longest-Common-Prefix Array Computation

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q3596712)