Succinct indexes for reporting discriminating and generic words

We consider the problem of indexing a collection DD of D strings (documents) of total n characters from an alphabet set of size σ, such that whenever a pattern P (of p   characters) and an integer τ∈[1,D]τ∈[1,D] come as a query, we can efficiently report all (i) maximal generic words and (ii) minimal discriminating words as defined below:•maximal generic word is a maximal extension of P occurring in at least τ documents.•minimal discriminating word is a minimal extension of P occurring in at most τ documents.These problems were introduced by Kucherov et al. (SPIRE) [8], they proposed indexes occupying O(nlog⁡n)O(nlog⁡n) bits with query times O(p+output)O(p+output) and O(p+log⁡log⁡n+output)O(p+log⁡log⁡n+output) for Problem (i) and Problem (ii) respectively. The query time for Problem (ii) is later improved to optimal O(p+output)O(p+output) by Gawrychowski et al. (SPIRE) [6]. In this paper, we describe succinct indexes of nlog⁡σ+o(nlog⁡σ)+O(n)nlog⁡σ+o(nlog⁡σ)+O(n) bits space with near-optimal query times i.e., O(p+log⁡log⁡n+output)O(p+log⁡log⁡n+output) for both these problems.