Algorithms for Anti-Powers in Strings

Badkobeh, Golnaz; Fici, Gabriele and Puglisi, Simon. 2018. Algorithms for Anti-Powers in Strings. Information Processing Letters, 137, pp. 57-60. ISSN 0020-0190 [Article]

[img]
Preview
Text
algorithms-anti-powers (1).pdf - Accepted Version
Available under License Creative Commons Attribution.

Download (365kB) | Preview

Abstract or Description

A string S[1, n] is a power (or tandem repeat) of order k and period n/k if it can decomposed into k consecutive equal-length blocks of letters. Powers and periods are fundamental to string processing, and algorithms for their efficient computation have wide application and are heavily studied. Recently, Fici et al. (Proc. ICALP 2016) defined an anti-power of order k to be a string composed of k pairwise-distinct blocks of the same length (n/k, called anti-period). Anti-powers are a natural converse to powers, and are objects of combinatorial interest in their own right. In this paper we initiate the algorithmic study of anti-powers. Given a string S, we describe an optimal algorithm for locating all substrings of S that are anti powers of a specified order. The optimality of the algorithm follows form a combinatorial lemma that provides a lower bound on the number of distinct anti-powers of a given order: we prove that a string of length n can contain Θ(n2/k) distinct anti-powers of order k.

Item Type:

Article

Identification Number (DOI):

https://doi.org/10.1016/j.ipl.2018.05.003

Keywords:

Anti-powers, Algorithms, Combinatorics on words

Departments, Centres and Research Units:

Computing

Dates:

DateEvent
15 May 2018Accepted
18 May 2018Published

Item ID:

23334

Date Deposited:

17 May 2018 11:37

Last Modified:

15 May 2019 01:26

Peer Reviewed:

Yes, this version has been peer-reviewed.

URI:

https://research.gold.ac.uk/id/eprint/23334

View statistics for this item...

Edit Record Edit Record (login required)