Substring range reporting

DOI10.1007/S00453-012-9733-4MaRDI QIDQ517792zbMATH OpenOpenAlexDBLPWikidataFDO

Authors Philip Bille, Inge Li Gørtz

Publication date 27 March 2017

Published in Algorithmica (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1007/s00453-012-9733-4

zbMATH Keywords

gapsstring indexingrange reportingposition-restricted substring searching

Mathematics Subject Classification ID

Data structures (68P05) Algorithms on strings (68W32)

Recommendations

• Substring Range Reporting
• Position-Restricted Substring Searching
• Position-restricted substring searching over small alphabets
• On position restricted substring searching in succinct space
• Succinct Orthogonal Range Search Structures on a Grid with Applications to Text Indexing

Cites work

• scientific article; zbMATH DE number 5485435 (Why is no real title available?)
• scientific article; zbMATH DE number 6146456 (Why is no real title available?)
• Algorithms on Strings, Trees and Sequences
• Bounded ordered dictionaries in O(log log N) time and O(n) space
• Design and implementation of an efficient priority queue
• Deterministic dictionaries
• Deterministic sorting in O(nloglogn) time and linear space
• Errata for ``Faster index for property matching
• Faster index for property matching
• Filtering Search: A New Approach to Query-Answering
• Finding patterns in given intervals
• Improved algorithms for the range next value problem and applications
• Improved data structures for the orthogonal range successor problem
• Indexing factors with gaps
• On dynamic range reporting in one dimension
• On the sorting-complexity of suffix tree construction
• Optimal prefix and suffix queries on texts
• Optimal static range reporting in one dimension
• Orthogonal range searching on the RAM, revisited
• Position-Restricted Substring Searching
• Preserving order in a forest in less than logarithmic time and linear space
• Property matching and weighted matching
• Range non-overlapping indexing
• Rank and select revisited and extended
• Space efficient dynamic stabbing with fast queries
• Space-Efficient and Fast Algorithms for Multidimensional Dominance Reporting and Counting
• Storing a Sparse Table with 0 (1) Worst Case Access Time
• Succinct Orthogonal Range Search Structures on a Grid with Applications to Text Indexing
• Time-space trade-offs for predecessor search

Cited in

(11)

• scientific article; zbMATH DE number 7651193 (Why is no real title available?)
• Longest common prefix with mismatches
• Reporting consecutive substring occurrences under bounded gap constraints
• I/O-efficient data structures for non-overlapping indexing
• String indexing for top-\(k\) close consecutive occurrences
• Position-Restricted Substring Searching
• Position-restricted substring searching over small alphabets
• Gapped indexing for consecutive occurrences
• Reporting consecutive substring occurrences under bounded gap constraints
• On position restricted substring searching in succinct space
• Substring Range Reporting

This page was built for publication: Substring range reporting

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q517792)