Computing the Antiperiod(s) of a String

Tools

Alamro, Hayam; Badkobeh, Golnaz; Belazzougui, Djamal; Iliopoulos, Costas S. and Puglisi, Simon J.. 2019. 'Computing the Antiperiod(s) of a String'. In: 30th Annual Symposium on Combinatorial Pattern Matching. Pisa, Italy 18-20 June 2019. [Conference or Workshop Item]

Preview

Text
Computing_the_antiperiod_of_a_string.pdf - Published Version
Available under License Creative Commons Attribution.
Download (103kB) | Preview

Official URL: https://drops.dagstuhl.de/opus/volltexte/2019/1050...

Abstract or Description

A string S[1, n] is a power (or repetition or tandem repeat) of order k and period n/k, if it can be decomposed into k consecutive identical blocks each n/k letters in length. Powers and periods are fundamental structures in the study of strings and algorithms to compute them efficiently have been widely studied. Recently, Fici et al. (Proc. ICALP 2016) introduced an antipower of order k to be a string composed of k distinct blocks of the same length, n/k, called the antiperiod. Antipowers are a natural converse to powers, and are objects of combinatorial interest in their own right. In this paper, we describe efficient algorithm for computing the smallest antiperiod t of a string S of length n in O(n log∗ t) time. We also describe an algorithm to compute all the antiperiods of S that runs in O(n log n) time.

Item Type:

Conference or Workshop Item (Paper)

Identification Number (DOI):

https://doi.org/10.4230/LIPIcs.CPM.2019.32

Additional Information:

This work was supported by the Academy of Finland under grant 319454.

Keywords:

antiperiod, antipower, power, period, repetition, run, string

Departments, Centres and Research Units:

Computing

Dates: