Creative Commons Attribution-NoDerivs 3.0 Unported license (CC BY-ND 3.0)when quoting this document, please refer to the following
DOI: 10.4230/LIPIcs.STACS.2013.245
URN: urn:nbn:de:0030-drops-39387
URL: https://drops.dagstuhl.de/opus/volltexte/2013/3938/
Kociumaka, Tomasz ; Radoszewski, Jakub ; Rytter, Wojciech
Fast Algorithms for Abelian Periods in Words and Greatest Common Divisor Queries
| pdf-format: |
|
Abstract
We present efficient algorithms computing all Abelian periods of two types in a word. Regular Abelian periods are computed in O(n log log{n}) randomized time which improves over the best previously known algorithm by almost a factor of n. The other algorithm, for full Abelian periods, works in O(n) time. As a tool we develop an O(n) time construction of a data structure that allows O(1) time gcd(i,j) queries for all 1 <= i,j <= n, this is a result of independent interest.
BibTeX - Entry
@InProceedings{kociumaka_et_al:LIPIcs:2013:3938,
author = {Tomasz Kociumaka and Jakub Radoszewski and Wojciech Rytter},
title = {{Fast Algorithms for Abelian Periods in Words and Greatest Common Divisor Queries}},
booktitle = {30th International Symposium on Theoretical Aspects of Computer Science (STACS 2013)},
pages = {245--256},
series = {Leibniz International Proceedings in Informatics (LIPIcs)},
ISBN = {978-3-939897-50-7},
ISSN = {1868-8969},
year = {2013},
volume = {20},
editor = {Natacha Portier and Thomas Wilke},
publisher = {Schloss Dagstuhl--Leibniz-Zentrum fuer Informatik},
address = {Dagstuhl, Germany},
URL = {http://drops.dagstuhl.de/opus/volltexte/2013/3938},
URN = {urn:nbn:de:0030-drops-39387},
doi = {10.4230/LIPIcs.STACS.2013.245},
annote = {Keywords: Abelian period, greatest common divisor}
}
| Keywords: | Abelian period, greatest common divisor | |
| Seminar: | 30th International Symposium on Theoretical Aspects of Computer Science (STACS 2013) | |
| Issue date: | 2013 | |
| Date of publication: | 26.02.2013 |
