Constructing suffix arrays in linear time
From MaRDI portal
Publication:2569391
DOI10.1016/j.jda.2004.08.019zbMath1101.68505OpenAlexW2064184672MaRDI QIDQ2569391
Jeong Seop Sim, Dong Kyue Kim, Heejin Park, Kun Soo Park
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.019
Related Items (30)
Faster index for property matching ⋮ Indexing factors with gaps ⋮ Suffix-sorting via Shannon-Fano-Elias codes ⋮ Efficient computation of substring equivalence classes with suffix arrays ⋮ The longest common extension problem revisited and applications to approximate string searching ⋮ Indexing a sequence for mapping reads with a single mismatch ⋮ A new efficient indexing algorithm for one-dimensional real scaled patterns ⋮ Finding range minima in the middle: approximations and applications ⋮ Linear-time construction of two-dimensional suffix trees ⋮ Online algorithms for finding distinct substrings with length and multiple prefix and suffix conditions ⋮ The indexing for one-dimensional proportionally-scaled strings ⋮ The parameterized suffix tray ⋮ The longest common substring problem ⋮ Algorithms and combinatorial properties on shortest unique palindromic substrings ⋮ 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 ⋮ Inducing enhanced suffix arrays for string collections ⋮ Computing longest previous factor in linear time and applications ⋮ Spaces, Trees, and Colors ⋮ Dynamic extended suffix arrays ⋮ Forty Years of Text Indexing ⋮ On suffix extensions in suffix trees ⋮ Errata for ``Faster index for property matching ⋮ Indexing Circular Patterns ⋮ Efficient indexing algorithms for one-dimensional discretely-scaled strings ⋮ THE VIRTUAL SUFFIX TREE ⋮ Improved and extended locating functionality on compressed suffix arrays ⋮ Suffix trays and suffix trists: structures for faster text indexing
Cites Work
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- The smallest automaton recognizing the subwords of a text
- An optimal algorithm for computing the repetitions in a word
- On-line construction of suffix trees
- Space Efficient Suffix Trees
- Symmetry breaking for suffix tree construction
- Suffix Arrays: A New Method for On-Line String Searches
- Compressed suffix arrays and suffix trees with applications to text indexing and string matching (extended abstract)
- Fast Lightweight Suffix Array Construction and Checking
- Space Efficient Linear Time Construction of Suffix Arrays
- Recursive Star-Tree Parallel Data Structure
- A Space-Economical Suffix Tree Construction Algorithm
- On the sorting-complexity of suffix tree construction
- Optimal parallel suffix tree construction
This page was built for publication: Constructing suffix arrays in linear time
