Research Online

Logo

Goldsmiths - University of London

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]

[img]
Preview
Text
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):

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:

DateEvent
18 March 2019Accepted
2019Published

Event Location:

Pisa, Italy

Date range:

18-20 June 2019

Item ID:

28017

Date Deposited:

10 Jan 2020 17:02

Last Modified:

11 Jan 2020 17:30

URI:

http://research.gold.ac.uk/id/eprint/28017

View statistics for this item...

Edit Record Edit Record (login required)