Linear work suffix array construction
From MaRDI portal
Publication:3455222
DOI10.1145/1217856.1217858zbMath1326.68111OpenAlexW2067974452MaRDI QIDQ3455222
Stefan Burkhardt, Peter Sanders, Juha Kärkkäinen
Publication date: 4 December 2015
Published in: Journal of the ACM (Search for Journal in Brave)
Full work available at URL: https://doi.org/10.1145/1217856.1217858
Related Items
Extended suffix array construction using Lyndon factors, Engineering a lightweight external memory suffix array construction algorithm, Faster average case low memory semi-external construction of the Burrows-Wheeler transform, Blocksequences of \(k\)-local words, Order-preserving pattern matching with \(k\) mismatches, Efficient computation of sequence mappability, Universal Reconstruction of a String, Lightweight LCP construction for very large collections of strings, Time-Space Trade-Offs for Longest Common Extensions, Faster index for property matching, Suffix-sorting via Shannon-Fano-Elias codes, Can Burrows-Wheeler transform be replaced in chain code compression?, Efficient computation of substring equivalence classes with suffix arrays, Kings, Name Days, Lazy Servants and Magic, Lempel Ziv Computation in Small Space (LZ-CISS), Compressed property suffix trees, Longest Gapped Repeats and Palindromes, Lightweight algorithms for constructing and inverting the BWT of string collections, Optimal in-place suffix sorting, Longest $$\alpha $$-Gapped Repeat and Palindrome, Design and analysis of periodic multiple seeds, On Prefix/Suffix-Square Free Words, \(p\)-suffix sorting as arithmetic coding, Property Suffix Array with Applications in Indexing Weighted Sequences, String Indexing with Compressed Patterns, Fast computation of a string duplication history under no-breakpoint-reuse, Indexing a sequence for mapping reads with a single mismatch, Parallel suffix sorting for large string analytics, Efficient chain code compression with interpolative coding, String Covering: A Survey, Quantum algorithm for lexicographically minimal string rotation, The “Runs” Theorem, Online algorithms for finding distinct substrings with length and multiple prefix and suffix conditions, Subsequences in bounded ranges: matching and analysis problems, A survey of string orderings and their application to the Burrows-Wheeler transform, Constructing and indexing the bijective and extended Burrows-Wheeler transform, A \textit{really} simple approximation of smallest grammar, The parameterized suffix tray, Tighter bounds and optimal algorithms for all maximal \(\alpha\)-gapped repeats and palindromes. Finding all maximal \(\alpha\)-gapped repeats and palindromes in optimal worst case time on integer alphabets, Unnamed Item, The longest common substring problem, Computing Longest Single-arm-gapped Palindromes in a String, Parallel algorithms for Burrows-Wheeler compression and decompression, Algorithms and combinatorial properties on shortest unique palindromic substrings, A bijective variant of the Burrows-Wheeler transform using \(V\)-order, Hide and seek with repetitions, Simple and efficient LZW-compressed multiple pattern matching, Time-space trade-offs for longest common extensions, The pseudopalindromic completion of regular languages, Prefix-suffix duplication, An algorithmic toolbox for periodic partial words, Universal compressed text indexing, Alphabet-independent linear-time construction of compressed suffix arrays using \(o(n \log n)\)-bit working space, Efficient Computation of 2-Covers of a String., Practical Performance of Space Efficient Data Structures for Longest Common Extensions., \(k\)-abelian pattern matching, Detecting One-Variable Patterns, Fast BWT in small space by blockwise suffix sorting, Faster suffix sorting, Binary block order Rouen transform, Fast compressed self-indexes with deterministic linear-time construction, Linear-time computation of prefix table for weighted strings {\&} applications, On Wavelet Tree Construction, Lightweight BWT Construction for Very Large String Collections, Inducing enhanced suffix arrays for string collections, Efficient algorithms for the longest common subsequence in \(k\)-length substrings, A quick tour on suffix arrays and compressed suffix arrays, Spaces, Trees, and Colors, Dynamic extended suffix arrays, Nearly \(k\)-universal words -- investigating a part of Simon's congruence, On suffix extensions in suffix trees, Unnamed Item, Errata for ``Faster index for property matching, Lempel-Ziv factorization powered by space efficient suffix trees, Indexing Circular Patterns, Unnamed Item, Parallel computation of the Burrows Wheeler transform in compact space, Efficient computation of longest single-arm-gapped palindromes in a string, Universal reconstruction of a string, The alternating BWT: an algorithmic perspective, Online algorithms for constructing linear-size suffix trie, A new class of searchable and provably highly compressible string transformations, Searching for gapped palindromes, THE VIRTUAL SUFFIX TREE, Bicriteria Data Compression, Small-space LCE data structure with constant-time queries, Orthogonal Range Searching for Text Indexing, Improved and extended locating functionality on compressed suffix arrays, Inducing Suffix and LCP Arrays in External Memory, Lazy Lempel-Ziv Factorization Algorithms, LCP Array Construction in External Memory, Fast Compressed Self-Indexes with Deterministic Linear-Time Construction, Nearly \(k\)-universal words -- investigating a part of Simon's congruence, Suffix trays and suffix trists: structures for faster text indexing, One-variable word equations in linear time
