Computing the Antiperiod(s) of a String
Loading...
Date
2019-06-18
Journal Title
Journal ISSN
Volume Title
Publisher
Schloss Dagstuhl--Leibniz-Zentrum fuer Informatik
Abstract
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 of length n/k. 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. An arbitrary string will have antiperiod t if it is prefix of an antipower with antiperiod t.
In this paper, we describe efficient algorithm for computing the smallest antiperiod of a string S of length n in O(n) time. We also describe an algorithm to compute all the antiperiods of S that runs in O(n log n) time.
Description
Keywords
antiperiod, antipower, power, period, repetition, run, string