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].

68P05 Data structures
Full Text: DOI