Position-restricted substring searching over small alphabets

We consider the problem of indexing a given text T[0...n−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.