We propose the first subquadratic-time algorithms to a number of natural problems in abelian pattern matching (also called jumbled pattern matching) for strings over a constant-sized alphabet. Two strings are considered equivalent in this model if the numbers of occurrences of respective symbols in both of them, specified by their so-called Parikh vectors, are the same. We propose the following algorithms for a string of length n: 1. Counting and finding longest/shortest abelian squares in O(n~2/ log~2 n) time. Abelian squares were first considered by Erdoes (1961); Cummings and Smyth (1997) proposed an O(n~2)-time algorithm for computing them. 2. Computing all shortest (general) abelian periods in O(n~2/(log n)~(1/2)) time. Abelian periods were introduced by Constantinescu and Ilie (2006) and the previous, quadratic-time algorithms for their computation were given by Fici et al. (2011) for a constant-sized alphabet and by Crochemore et al. (2012) for a general alphabet. 3. Finding all abelian covers in O(n~2/ log n) time. Abelian covers were defined by Matsuda et al. (2014). 4. Computing abelian border array in O(n~2/ log~2 n) time. This work can be viewed as a continuation of a recent very active line of research on subquadratic space and time jumbled indexing for binary and constant-sized alphabets (e.g., Moosa and Rahman, 2012). All our algorithms work in linear space.
展开▼
