Substring complexity in sublinear space
From MaRDI portal
Cites work
- A Functional Approach to Data Structures and Its Use in Multidimensional Searching
- A general Sequential Time-Space Tradeoff for Finding Unique Elements
- A Time-Space Tradeoff for Sorting on a General Sequential Model of Computation
- A universal algorithm for sequential data compression
- Algorithms on Strings
- Algorithms on Strings, Trees and Sequences
- Approximate Hamming distance in a stream
- Approximating LZ77 via Small-Space Multiple-Pattern Matching
- Approximating text-to-pattern Hamming distances
- At the roots of dictionary compression: string attractors
- Breaking a time-and-space barrier in constructing full-text indices
- Breaking the \(\mathcal{O}(n)\)-barrier in the construction of compressed suffix arrays and suffix trees
- Compressed Suffix Arrays and Suffix Trees with Applications to Text Indexing and String Matching
- Computing the longest previous factor
- Dictionary matching in a stream
- Dynamic text and static pattern matching
- Efficient computation of shortest absent words in a genomic sequence
- Elastic-Degenerate String Matching via Fast Matrix Multiplication
- Element distinctness, frequency moments, and sliding windows
- Even faster elastic-degenerate string matching via fast matrix multiplication
- Exact and Approximate Pattern Matching in the Streaming Model
- Factorizing words over an ordered alphabet
- Fully functional suffix trees and optimal text searching in BWT-runs bounded space
- Grammar-based codes: a new class of universal lossless source codes
- scientific article; zbMATH DE number 1512678 (Why is no real title available?)
- scientific article; zbMATH DE number 7651096 (Why is no real title available?)
- scientific article; zbMATH DE number 7651106 (Why is no real title available?)
- Indexing compressed text
- Lempel-Ziv-like parsing in small space
- Linear time construction of compressed text indices in compact space
- Linear work suffix array construction
- Linear-time algorithm for long LCF with k mismatches
- Locally Consistent Parsing for Text Indexing in Small Space
- Near-optimal search time in -optimal space
- Near-Optimal Time-Space Tradeoff for Element Distinctness
- On compressing and indexing repetitive sequences
- On the combinatorics of finite words
- Optimal-Time Dictionary-Compressed Indexes
- Real-Time Streaming Multi-Pattern Search for Constant Alphabet
- Real-time streaming string-matching
- Simple real-time constant-space string matching
- Space-efficient construction of compressed indexes in deterministic linear time
- Streaming \(k\)-mismatch with error correcting and applications
- Streaming Dictionary Matching with Mismatches
- Streaming pattern matching with \(d\) wildcards
- String synchronizing sets: sublinear-time BWT construction and optimal LCE data structure
- Sublinear algorithms for approximating string compressibility
- Sublinear space algorithms for the longest common substring problem
- Suffix Arrays: A New Method for On-Line String Searches
- Suffix trays and suffix trists: structures for faster text indexing
- The \(k\)-mismatch problem revisited
- The streaming \(k\)-mismatch problem
- Three approaches to the quantitative definition of information*
- Time-space trade-offs for the longest common substring problem
- Time-space-optimal string matching
- Toward a Definitive Compressibility Measure for Repetitive Sequences
- Towards a definitive measure of repetitiveness
- Towards optimal approximate streaming pattern matching by matching multiple patterns in multiple streams
- Two-way string-matching
- Uniqueness Theorems for Periodic Functions
- Word assembly through minimal forbidden words
- Words and special factors
Cited in
(2)
This page was built for publication: Substring complexity in sublinear space
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q6953209)
