Dynamic extended suffix arrays

DOI10.1016/j.jda.2009.02.007zbMath1201.68044WikidataQ56485249 ScholiaQ56485249MaRDI QIDQ972366

Thierry Lecroq, Laurent Mouchard, Martine Léonard, Mikaël Salson

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

FM-index; algorithm design; edit operations; self-index data structures; dynamic suffix array

Mathematics Subject Classification ID

68Q25: Analysis of algorithms and problem complexity

68P05: Data structures

68W32: Algorithms on strings

Related Items

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, On suffix extensions in suffix trees, Dynamic index and LZ factorization in compressed space, Semi-dynamic Compact Index for Short Patterns and Succinct van Emde Boas Tree

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• A four-stage algorithm for updating a Burrows-Wheeler transform
• Compressed suffix trees with full functionality
• Rank and select revisited and extended
• Constructing suffix arrays in linear time
• Space efficient linear time construction of suffix arrays
• Compressed representations of sequences and full-text indexes
• Linear work suffix array construction
• An Improved Succinct Representation for Dynamic k-ary Trees
• A Space-Economical Suffix Tree Construction Algorithm
• Algorithms on Strings, Trees and Sequences
• Dynamic entropy-compressed sequences and full-text indexes
• Combinatorial Pattern Matching
• Fully-Compressed Suffix Trees
• Improved Dynamic Rank-Select Entropy-Bound Structures