New for: D1, D2, D3, D4, D5
standard stringology — jumbled pattern matching.
Moosa and Rahman have given a construction of an index for
jumbled pattern matching for the case of binary alphabets. They posed
as an open problem the efficient solution for the case of larger alphabets.
In this paper we provide an index for any constant-sized alphabet. We
obtain the first o(n^2) time and space construction of an index with o(n)
query time. In particular, our data structure can be implemented with
O(n^(2−δ)) space and O(m^{2σδ}) query time for any δ > 0, where m is the
length of the pattern and σ is the size of the alphabet (σ = O(1)). We
also break the barrier of quadratic preprocessing time.