Computing the Antiperiod(s) of a String

Simple item page
dc.contributor.authorAlamro, Hayam
dc.contributor.authorBadkobeh, Golnaz
dc.contributor.authorBelazzougui, Djamal
dc.contributor.authorIliopoulos, Costas S.
dc.contributor.authorPuglisi, Simon J.
dc.date.accessioned2019-06-10T10:18:51Z
dc.date.available2019-06-10T10:18:51Z
dc.date.issued2019-06-18
dc.description.abstractA 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.fr_FR
dc.identifier.isbn978-3-95977-103-0fr_FR
dc.identifier.urihttp://dl.cerist.dz/handle/CERIST/940
dc.publisherSchloss Dagstuhl--Leibniz-Zentrum fuer Informatikfr_FR
dc.relation.ispartofseries30th Annual Symposium on Combinatorial Pattern Matching (CPM 2019);128
dc.relation.pages1-11fr_FR
dc.relation.placePisa, Italyfr_FR
dc.structureCalcul pervasif et mobile (Pervasive and Mobile Computing group)fr_FR
dc.subjectantiperiodfr_FR
dc.subjectantipowerfr_FR
dc.subjectpowerfr_FR
dc.subjectperiodfr_FR
dc.subjectrepetitionfr_FR
dc.subjectrunfr_FR
dc.subjectstringfr_FR
dc.titleComputing the Antiperiod(s) of a Stringfr_FR
dc.typeConference paper
Files
Collections
International Conference Papers