Article ID | Journal | Published Year | Pages | File Type |
---|---|---|---|---|
4952358 | Theoretical Computer Science | 2016 | 9 Pages |
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.
Related Topics
Physical Sciences and Engineering
Computer Science
Computational Theory and Mathematics
Authors
Gabriele Fici, Tomasz Kociumaka, Thierry Lecroq, Arnaud Lefebvre, Ãlise Prieur-Gaston,