We introduce efficient data structures for an indexing problem in non-standard stringology - jumbled pattern matching. Moosa and Rahman [J. Discr. Alg., 2012] gave an index for jumbled pattern matching for the case of binary alphabets with O( n~2/log~2n )-time construction. They posed as an open problem an efficient solution for larger alphabets. In this paper we provide an index for any constant-sized alphabet. We obtain the first o(n~2 )-space construction of an index with o{n) query time. It can be built in O(n~2) time. Precisely, our data structure can be implemented with O(n~(2-δ)) space and O(m~(2σ-1)δ) query time for any δ ＞ 0, where m is the length of the pattern and σ is the alphabet size (σ = O(1)). We also break the barrier of quadratic construction time for non-binary constant alphabet simultaneously obtaining poly-logarithmic query time.
展开▼
