Space efficient linear time construction of suffix arrays
From MaRDI portal
Publication:2569393
DOI10.1016/j.jda.2004.08.002zbMath1101.68506OpenAlexW2118703123MaRDI QIDQ2569393
Publication date: 27 October 2005
Published in: Journal of Discrete Algorithms (Search for Journal in Brave)
Full work available at URL: https://doi.org/10.1016/j.jda.2004.08.002
Related Items
Faster index for property matching, Computing the original eBWT faster, simpler, and with less memory, Indexing factors with gaps, Optimal suffix sorting and LCP array construction for constant alphabets, Suffix-sorting via Shannon-Fano-Elias codes, Efficient computation of substring equivalence classes with suffix arrays, Locating maximal approximate runs in a string, Kings, Name Days, Lazy Servants and Magic, Lightweight algorithms for constructing and inverting the BWT of string collections, An Opportunistic Text Indexing Structure Based on Run Length Encoding, The longest common extension problem revisited and applications to approximate string searching, Efficient construction of the BWT for repetitive text using string compression, Indexing a sequence for mapping reads with a single mismatch, A new efficient indexing algorithm for one-dimensional real scaled patterns, Parallel suffix sorting for large string analytics, Linear-time construction of two-dimensional suffix trees, The “Runs” Theorem, Period recovery of strings over the Hamming and edit distances, Constructing and indexing the bijective and extended Burrows-Wheeler transform, The parameterized suffix tray, The longest common substring problem, Parallel algorithms for Burrows-Wheeler compression and decompression, Algorithms and combinatorial properties on shortest unique palindromic substrings, Faster semi-external suffix sorting, A simple yet time-optimal and linear-space algorithm for shortest unique substring queries, Counting suffix arrays and strings, Alphabet-independent linear-time construction of compressed suffix arrays using \(o(n \log n)\)-bit working space, Fast BWT in small space by blockwise suffix sorting, Fast compressed self-indexes with deterministic linear-time construction, Lightweight BWT Construction for Very Large String Collections, Inducing enhanced suffix arrays for string collections, Computing longest previous factor in linear time and applications, A quick tour on suffix arrays and compressed suffix arrays, Spaces, Trees, and Colors, Dynamic extended suffix arrays, Forty Years of Text Indexing, On suffix extensions in suffix trees, Unnamed Item, Errata for ``Faster index for property matching, Indexing Circular Patterns, THE VIRTUAL SUFFIX TREE, Improved and extended locating functionality on compressed suffix arrays, Inducing Suffix and LCP Arrays in External Memory, Suffix trays and suffix trists: structures for faster text indexing
Uses Software
Cites Work
- Replacing suffix trees with enhanced suffix arrays
- On-line construction of suffix trees
- Faster suffix sorting
- Suffix Arrays: A New Method for On-Line String Searches
- Linear-Time Construction of Suffix Arrays
- A Space-Economical Suffix Tree Construction Algorithm
- Algorithms on Strings, Trees and Sequences
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
