Range Non-Overlapping Indexing

Details Range Non-Overlapping Indexing Range Non-Overlapping Indexing

2009-09-26

arxiv.org/abs/0909.4893v2

Computer Science

Data Structures and Algorithms

10 pages

Scientific paper

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(n\log^\epsilon n) space for some 0<\epsilon<1 and O(m + \log\log n + occ_{ij,NO}) query time.

Affiliated with

Also associated with

No associations

Rating

Range Non-Overlapping Indexing does not yet have a rating. At this time, there are no reviews or comments for this scientific paper.

If you have personal experience with Range Non-Overlapping Indexing, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Range Non-Overlapping Indexing will most certainly appreciate the feedback.

Rate now

Comments { 0 }

Profile ID: LFWR-SCP-O-316345