Computing the Antiperiod(s) of a String

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]

Computing_the_antiperiod_of_a_string.pdf - Published Version
Available under License Creative Commons Attribution.

Download (103kB) | Preview

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):

Additional Information:

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


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

Departments, Centres and Research Units:



18 March 2019Accepted

Event Location:

Pisa, Italy

Date range:

18-20 June 2019

Item ID:


Date Deposited:

10 Jan 2020 17:02

Last Modified:

12 Jun 2021 18:58


View statistics for this item...

Edit Record Edit Record (login required)