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 o c c ℓ , r occurrences of P in T [ ℓ . . . r ] . In this paper, we propose an O ( n log ⁡ σ ) -word space index with O ( p + o c c ℓ , r log ⁡ 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 + o c c ℓ , r log ϵ ⁡ n ) query time, where ϵ > 0 is an arbitrarily small positive constant. [ABSTRACT FROM AUTHOR]