Position-Restricted Substring Searching Over Small Alphabets

Keywords

Orthogonal range reporting; Pattern matching; String searching; Text indexing

Abstract

We consider the problem of indexing a given text T[0n−1] of n characters over an alphabet set Σ of size σ, in order to answer the position-restricted substring searching queries. The query input consists of a pattern P (of length p) and two indices ℓ and r and the output is the set of all occℓ,r occurrences of P in T[ℓr]. In this paper, we propose an O(nlog⁡σ)-word space index with O(p+occℓ,rlog⁡log⁡n) query time. Our solution is interesting when the alphabet size is small. For example, when the alphabet set is of constant size, we achieve significant improvement over the previously best-known linear space index by Navarro and Nekrich [SWAT 2012] with O(p+occℓ,rlogϵ⁡n) query time, where ϵ>0 is an arbitrarily small positive constant.

Publication Date

9-1-2017

Publication Title

Journal of Discrete Algorithms

Volume

46-47

Number of Pages

36-39

Document Type

Article

Personal Identifier

scopus

DOI Link

https://doi.org/10.1016/j.jda.2017.10.001

Socpus ID

85031325337 (Scopus)

Source API URL

https://api.elsevier.com/content/abstract/scopus_id/85031325337

This document is currently not available here.

Share

COinS