Fast computation of abelian runs

Abstract

Given a word w and a Parikh vector P, an abelian run of period P in w is a maximal occurrence of a substring of w having abelian period P. Our main result is an online algorithm that, given a word w of length n over an alphabet of cardinality σ and a Parikh vector P, returns all the abelian runs of period P in w in time O(n) and space O(σ+p), where p is the norm of P, i.e., the sum of its components. We also present an online algorithm that computes all the abelian runs with periods of norm p in w in time O(np), for any given norm p. Finally, we give an O(n2)-time offline randomized algorithm for computing all the abelian runs of w. Its deterministic counterpart runs in O(n2log⁡σ) time.