AG 1, AG 2, AG 3, AG 4, AG 5, RG1, SWS, MMCI   Info

AG Audience

English

30 Minutes

Saarbrücken

We introduce efficient data structures for the indexing problem in non-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.

Pawel Gawrychowski

--email hidden

passcode not visible

logged in users only