Range Non-Overlapping Indexing

2009/09/26 by Hagai Cohen, Cohen, Hagai, Ely Porat +1 · 1 citation
Biochemistry, Genetics and Molecular Biology · Computer Science · #Algorithms and Data Compression #DNA and Biological Computing #Data Structures and Algorithms (cs.DS) #FOS: Computer and information sciences #semigroups and automata theory

paper · pdf · doi:10.48550/arxiv.0909.4893

openalex publication_date 2009/09/26 · openalex created_date 2025/10/10 · openalex updated_date 2026/07/28

Abstract

We study the non-overlapping indexing problem: Given a text T, preprocess it so that you can answer queries of the form: given a pattern P, report the maximal set of non-overlapping occurrences of P in T. A generalization of this problem is the range non-overlapping indexing where in addition we are given two indexes i,j to report the maximal set of non-overlapping occurrences between these two indexes. We suggest new solutions for these problems. For the non-overlapping problem our solution uses O(n) space with query time of O(m + occ_NO). For the range non-overlapping problem we propose a solution with O(nlog^εn) space for some 0

Cited by

• Text Indexing: From Reporting to Counting

Related

• Gapped Indexing for Consecutive Occurrences
• Data Structures for Range Sorted Consecutive Occurrence Queries
• Compressed Indexing for Consecutive Occurrences
• Gapped String Indexing in Subquadratic Space and Sublinear Query Time
• An Algorithm for Optimized Searching using NON-Overlapping Iterative Neighbor intervals