2026-07-22T11:09:41Z https://drops.dagstuhl.de/oai

oai:drops-oai.dagstuhl.de:10503 2024-03-06T10:45:54Z ddc:004 open_access

Computing the Antiperiod(s) of a String Alamro, Hayam Badkobeh, Golnaz Belazzougui, Djamal Iliopoulos, Costas S. Puglisi, Simon J. antiperiod antipower power period repetition run string 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. Schloss Dagstuhl – Leibniz-Zentrum für Informatik Hayam Alamro and Golnaz Badkobeh and Djamal Belazzougui and Costas S. Iliopoulos and Simon J. Puglisi 2019 Is Part Of LIPIcs, Volume 128, 30th Annual Symposium on Combinatorial Pattern Matching (CPM 2019) InProceedings Text doc-type:ResearchArticle publishedVersion application/pdf doi:10.4230/LIPIcs.CPM.2019.32 urn:nbn:de:0030-drops-105035 https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.CPM.2019.32 eng https://creativecommons.org/licenses/by/3.0/legalcode