King's College London

Research portal

Computing the Antiperiod(s) of a String

Research output: Chapter in Book/Report/Conference proceedingConference paperpeer-review

Hayam Mohammed A Alamro, Golnaz Badkobeh, Djamal Belazzougui, Costas Iliopoulos, Simon J. Puglisi

Original languageEnglish
Title of host publication30th Annual Symposium on Combinatorial Pattern Matching, CPM 2019
EditorsNadia Pisanti, Solon P. Pissis
Place of PublicationDagstuhl, Germany
PublisherSchloss Dagstuhl--Leibniz-Zentrum fuer Informatik
Number of pages11
Volume128
ISBN (Electronic)978-3-95977-103-0
DOIs
Accepted/In press18 Mar 2019
Published2019

Documents

King's Authors

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.

Download statistics

No data available

View graph of relations

© 2020 King's College London | Strand | London WC2R 2LS | England | United Kingdom | Tel +44 (0)20 7836 5454