Advertisement
Published in:
2015 | OriginalPaper | Chapter
Succinct Non-overlapping Indexing
Authors : Arnab Ganguly, Rahul Shah, Sharma V. Thankachan
Published in: Combinatorial Pattern Matching
Publisher: Springer International Publishing
Activate our intelligent search to find suitable subject content or patents.
Select sections of text to find matching patents with Artificial Intelligence. powered by
Select sections of text to find additional relevant content using AI-assisted search. powered by
Abstract
Given a text \(\mathsf {T}\) having \(n\) characters, we consider the non-overlapping indexing problem defined as follows: pre-process \(\mathsf {T}\) into a data-structure, such that whenever a pattern \(P\) comes as input, we can report a maximal set of non-overlapping occurrences of \(P\) in \(\mathsf {T}\). The best known solution for this problem takes linear space, in which a suffix tree of \(\mathsf {T}\) is augmented with \(O(n)\)-word data structures. A query \(P\) can be answered in optimal \(O(|P|+\mathsf {nocc})\) time, where \(\mathsf {nocc}\) is the output size [Cohen and Porat, ISAAC 2009]. We present the following new result: let \(\mathsf {CSA}\) (not necessarily a compressed suffix array) be an index of \(\mathsf {T}\) that can compute (i) the suffix range of \(P\) in \(\mathsf {search}(P)\) time, and (ii) a suffix array or an inverse suffix array value in \(\mathsf {t_{SA}}\) time; then by using \(\mathsf {CSA}\) alone, we can answer a query \(P\) in \(O(\mathsf {search}(P)+ \mathsf {nocc}\cdot \mathsf {t_{SA}})\) time. Additionally, we present an improved result for a generalized version of this problem called range non-overlapping indexing.