Algorithms for anti-powers in strings

Show full item record



Permalink

http://hdl.handle.net/10138/308352

Citation

Badkobeh , G , Fici , G & Puglisi , S J 2018 , ' Algorithms for anti-powers in strings ' , Information Processing Letters , vol. 137 , pp. 57-60 . https://doi.org/10.1016/j.ipl.2018.05.003

Title: Algorithms for anti-powers in strings
Author: Badkobeh, Golnaz; Fici, Gabriele; Puglisi, Simon J.
Contributor: University of Helsinki, Department of Computer Science
Date: 2018-09
Language: eng
Number of pages: 4
Belongs to series: Information Processing Letters
ISSN: 0020-0190
URI: http://hdl.handle.net/10138/308352
Abstract: 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.
Subject: Anti-powers
Algorithms
Combinatorics on words
113 Computer and information sciences
Rights:


Files in this item

Total number of downloads: Loading...

Files Size Format View
main.pdf 364.4Kb PDF View/Open

This item appears in the following Collection(s)

Show full item record