Dynamic extended suffix arrays

DOI10.1016/J.JDA.2009.02.007MaRDI QIDQ972366zbMATH OpenOpenAlexWikidataFDO

Authors Thierry Lecroq, L. Mouchard, M. Salson, M. Léonard

Publication date 25 May 2010

Published in Journal of Discrete Algorithms (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1016/j.jda.2009.02.007

zbMATH Keywords

algorithm designdynamic suffix arrayedit operationsFM-indexself-index data structures

Mathematics Subject Classification ID

Data structures (68P05) Analysis of algorithms and problem complexity (68Q25) Algorithms on strings (68W32)

Recommendations

• Dynamic suffix array with polylogarithmic queries and updates
• Suffix arrays with a twist
• Extended suffix array construction using Lyndon factors
• An elegant algorithm for the construction of suffix arrays
• scientific article; zbMATH DE number 1615289
• Inducing enhanced suffix arrays for string collections
• Dynamic Fully-Compressed Suffix Trees
• scientific article; zbMATH DE number 7765421
• Linear-time construction of suffix arrays (extended abstract)

Cites work

• A four-stage algorithm for updating a Burrows-Wheeler transform
• A Space-Economical Suffix Tree Construction Algorithm
• Algorithms on Strings, Trees and Sequences
• An Improved Succinct Representation for Dynamic k-ary Trees
• Combinatorial Pattern Matching
• Compressed representations of sequences and full-text indexes
• Compressed suffix trees with full functionality
• Constructing suffix arrays in linear time
• Dynamic entropy-compressed sequences and full-text indexes
• Fully-Compressed Suffix Trees
• scientific article; zbMATH DE number 432779 (Why is no real title available?)
• scientific article; zbMATH DE number 5542185 (Why is no real title available?)
• scientific article; zbMATH DE number 1306892 (Why is no real title available?)
• scientific article; zbMATH DE number 1998345 (Why is no real title available?)
• scientific article; zbMATH DE number 2038723 (Why is no real title available?)
• scientific article; zbMATH DE number 2230164 (Why is no real title available?)
• Improved Dynamic Rank-Select Entropy-Bound Structures
• Linear work suffix array construction
• Rank and select revisited and extended
• Space efficient linear time construction of suffix arrays

Cited in

(12)

• On updating suffix tree labels
• Extended suffix array construction using Lyndon factors
• A linear time lower bound on McCreight and general updating algorithms for suffix trees
• Dynamic index and LZ factorization in compressed space
• Semi-dynamic compact index for short patterns and succinct van Emde Boas tree
• In-place update of suffix array while recoding words
• On the number of elements to reorder when updating a suffix array
• On-line suffix tree construction with reduced branching
• Using static suffix array in dynamic application: case of text compression by longest first substitution
• Position heaps: a simple and dynamic text indexing data structure
• scientific article; zbMATH DE number 7765421 (Why is no real title available?)
• On suffix extensions in suffix trees

This page was built for publication: Dynamic extended suffix arrays

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