On position restricted substring searching in succinct space

We study the position restricted substring searching (PRSS) problem, where the task is to index a text T[0…n−1]T[0…n−1] of n characters over an alphabet set Σ of size σ, in order to answer the following: given a query pattern P (of length p) and two indices ℓ and r  , report all occℓ,roccℓ,r occurrences of P   in T[ℓ…r]T[ℓ…r]. Known indexes take O(nlogn) bits or O(nlog1+ϵn) bits space, and answer this query in O(p+logn+occℓ,rlogn) time or in optimal O(p+occℓ,r)O(p+occℓ,r) time respectively, where ϵ   is any positive constant. The main drawback of these indexes is their space requirement of Ω(nlogn) bits, which can be much more than the optimal nlogσ bits to store the text T  . This paper addresses an open question asked by Mäkinen and Navarro [LATIN, 2006], which is whether it is possible to design a succinct index answering PRSS queries efficiently. We first study the hardness of this problem and prove the following result: a succinct (or a compact) index cannot answer PRSS queries efficiently in the pointer machine model, and also not in the RAM model unless bounds on the well-researched orthogonal range query problem improve. However, for the special case of sufficiently long query patterns, that is for p=Ω(log2+ϵn), we derive an |CSAf|+|CSAr|+o(n)|CSAf|+|CSAr|+o(n) bits index with optimal query time, where |CSAf||CSAf| and |CSAr||CSAr| are the space (in bits) of the compressed suffix arrays (with O(p)O(p) time for pattern search) of T   and T← (the reverse of T  ) respectively. The space can be reduced further to |CSAf|+o(n)|CSAf|+o(n) bits with a resulting query time will be O(p+occℓ,r+log3+ϵn). For the general case, where there is no restriction on pattern length, we obtain an O(1ϵ3nlogσ) bits index with O(p+occℓ,r+nϵ)O(p+occℓ,r+nϵ) query time. We use suffix sampling techniques to achieve these space-efficient indexes.