Substring range reporting

DOI10.1007/s00453-012-9733-4zbMath1360.68375OpenAlexW2915747377WikidataQ60554401 ScholiaQ60554401MaRDI QIDQ517792

Inge Li Gørtz, Philip Bille

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)

Related Items

Reporting consecutive substring occurrences under bounded gap constraints, String indexing for top-\(k\) close consecutive occurrences, Reporting Consecutive Substring Occurrences Under Bounded Gap Constraints, Position-restricted substring searching over small alphabets, Longest Common Prefix with Mismatches, Unnamed Item, Gapped indexing for consecutive occurrences, I/O-efficient data structures for non-overlapping indexing

Cites Work

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