# zbMATH — the first resource for mathematics

Range non-overlapping indexing. (English) Zbl 1273.68097
Dong, Yingfei (ed.) et al., Algorithms and computation. 20th international symposium, ISAAC 2009, Honolulu, Hawaii, USA, December 16–18, 2009. Proceedings. Berlin: Springer (ISBN 978-3-642-10630-9/pbk). Lecture Notes in Computer Science 5878, 1044-1053 (2009).
Summary: We study the non-overlapping indexing problem: Given a text $$T$$, preprocess it in order to 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 + \text{occ} _{\text{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 + \text{occ}_{ij,\text{NO}})$$ query time.
For the entire collection see [Zbl 1178.68008].

##### MSC:
 68P05 Data structures
Full Text: