TY - JOUR

T1 - Algorithms for anti-powers in strings

AU - Fici, Gabriele

AU - Badkobeh, Golnaz

AU - Puglisi, Simon J.

PY - 2018

Y1 - 2018

N2 - A string S[1,n] is a power (or tandem repeat) of order k and period n/k if it can be 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.

AB - A string S[1,n] is a power (or tandem repeat) of order k and period n/k if it can be 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.

KW - Algorithms

KW - Anti-powers

KW - Combinatorics on words

KW - Computer Science Applications1707 Computer Vision and Pattern Recognition

KW - Information Systems

KW - Signal Processing

KW - Theoretical Computer Science

KW - Algorithms

KW - Anti-powers

KW - Combinatorics on words

KW - Computer Science Applications1707 Computer Vision and Pattern Recognition

KW - Information Systems

KW - Signal Processing

KW - Theoretical Computer Science

UR - http://hdl.handle.net/10447/336069

M3 - Article

VL - 137

SP - 57

EP - 60

JO - Information Processing Letters

JF - Information Processing Letters

SN - 0020-0190

ER -