Gapped string indexing in subquadratic space and sublinear query time
From MaRDI portal
Cites work
- A general technique for searching in implicit sets via function inversion
- A Lower Bound for Jumbled Indexing
- Algorithms on Strings
- Algorithms on Strings, Trees and Sequences
- Alphabet-dependent string searching with wexponential search trees
- Clustered Integer 3SUM via Additive Combinatorics
- Color-distance oracles and snippets
- Conditional lower bounds for space/time tradeoffs
- Data structures meet cryptography: 3SUM with preprocessing
- Dictionary matching and indexing with errors and don't cares
- Efficient indexes for jumbled pattern matching with constant-sized alphabet
- Experimental algorithms. 10th international symposium, SEA 2011, Kolimpari, Chania, Crete, Greece, May 5--7, 2011. Proceedings
- Fast Pattern Matching in Strings
- Faster min-plus product for monotone instances
- Gapped indexing for consecutive occurrences
- scientific article; zbMATH DE number 1786458 (Why is no real title available?)
- scientific article; zbMATH DE number 1408945 (Why is no real title available?)
- Indexing factors with gaps
- INDEXING GAPPED-FACTORS USING A TREE
- Less space: indexing for queries with wildcards
- Log-logarithmic worst-case range queries are possible in space theta(N)
- More logarithmic-factor speedups for 3SUM, (median,+)-convolution, and some geometric 3SUM-hard problems
- On hardness of jumbled indexing
- Programming Techniques: Regular expression search algorithm
- Regular expression matching with multi-strings and intervals
- Rigorous Time/Space Trade-offs for Inverting Functions
- Space-efficient string indexing for wildcard pattern matching
- Storing a Sparse Table with 0 (1) Worst Case Access Time
- String indexing for patterns with wildcards
- String matching with variable length gaps
- Substring range reporting
- Suffix Arrays: A New Method for On-Line String Searches
- Suffix trays and suffix trists: structures for faster text indexing
- Time-optimal top-k document retrieval
- Weighted ancestors in suffix trees
Cited in
(2)
This page was built for publication: Gapped string indexing in subquadratic space and sublinear query time
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q6902709)
