Algorithms for anti-powers in strings

Abstract: 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 {em anti-power} of order

k

to be a string composed of

k

pairwise-distinct blocks of the same length (

n / k

, called {em 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

T h e t a (n^{2} / k)

distinct anti-powers of order

k

.

Review text

A concatenation of \(k\) identical copies of a string of length \(m\) is a power of order \(k\) (or \(k\)-power); the integer \(m\) is its period. A concatenation of \(k\) pairwise-distinct strings of identical length \(m\) is an anti-power of order \(k\) (or \(k\)-anti-power); the integer \(m\) is its anti-period. The authors show that every string of length \(n\) contains \(\Omega\left( n^{2}/k\right) \) anti-powers of order \(k\), and they provide an algorithm that finds, for a given string \(S\) of length \(n\), the locations of all substrings of \(S\) that are \(k\)-anti-powers. The algorithm is optimal since it works in \(O(n^{2}/k)\) time and \(O(n)\) space.

Recommendations

Cites work

Cited in

(9)

This page was built for publication: Algorithms for anti-powers in strings

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q1641162)