Research output: Chapter in Book/Report/Conference proceeding › Conference paper › peer-review

**Computing the Antiperiod(s) of a String.** / Alamro, Hayam Mohammed A; Badkobeh, Golnaz; Belazzougui, Djamal; Iliopoulos, Costas; Puglisi, Simon J.

Research output: Chapter in Book/Report/Conference proceeding › Conference paper › peer-review

Alamro, HMA, Badkobeh, G, Belazzougui, D, Iliopoulos, C & Puglisi, SJ 2019, Computing the Antiperiod(s) of a String. in N Pisanti & S P. Pissis (eds), *30th Annual Symposium on Combinatorial Pattern Matching, CPM 2019.* vol. 128, 32, Schloss Dagstuhl--Leibniz-Zentrum fuer Informatik, Dagstuhl, Germany. https://doi.org/10.4230/LIPIcs.CPM.2019.32

Alamro, H. M. A., Badkobeh, G., Belazzougui, D., Iliopoulos, C., & Puglisi, S. J. (2019). Computing the Antiperiod(s) of a String. In N. Pisanti, & S. P. Pissis (Eds.), *30th Annual Symposium on Combinatorial Pattern Matching, CPM 2019 *(Vol. 128). [32] Schloss Dagstuhl--Leibniz-Zentrum fuer Informatik. https://doi.org/10.4230/LIPIcs.CPM.2019.32

Alamro HMA, Badkobeh G, Belazzougui D, Iliopoulos C, Puglisi SJ. Computing the Antiperiod(s) of a String. In Pisanti N, P. Pissis S, editors, 30th Annual Symposium on Combinatorial Pattern Matching, CPM 2019. Vol. 128. Dagstuhl, Germany: Schloss Dagstuhl--Leibniz-Zentrum fuer Informatik. 2019. 32 https://doi.org/10.4230/LIPIcs.CPM.2019.32

@inbook{f849970afabd4dc58ba864ff0660a0ef,

title = "Computing the Antiperiod(s) of a String",

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.",

keywords = "Antiperiod, Antipower, Period, Power, Repetition, Run, String",

author = "Alamro, {Hayam Mohammed A} and Golnaz Badkobeh and Djamal Belazzougui and Costas Iliopoulos and Puglisi, {Simon J.}",

year = "2019",

doi = "10.4230/LIPIcs.CPM.2019.32",

language = "English",

volume = "128",

editor = "Pisanti, {Nadia } and {P. Pissis}, {Solon }",

booktitle = "30th Annual Symposium on Combinatorial Pattern Matching, CPM 2019",

publisher = "Schloss Dagstuhl--Leibniz-Zentrum fuer Informatik",

}

TY - CHAP

T1 - Computing the Antiperiod(s) of a String

AU - Alamro, Hayam Mohammed A

AU - Badkobeh, Golnaz

AU - Belazzougui, Djamal

AU - Iliopoulos, Costas

AU - Puglisi, Simon J.

PY - 2019

Y1 - 2019

N2 - 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.

AB - 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.

KW - Antiperiod

KW - Antipower

KW - Period

KW - Power

KW - Repetition

KW - Run

KW - String

UR - http://www.scopus.com/inward/record.url?scp=85068042601&partnerID=8YFLogxK

U2 - 10.4230/LIPIcs.CPM.2019.32

DO - 10.4230/LIPIcs.CPM.2019.32

M3 - Conference paper

VL - 128

BT - 30th Annual Symposium on Combinatorial Pattern Matching, CPM 2019

A2 - Pisanti, Nadia

A2 - P. Pissis, Solon

PB - Schloss Dagstuhl--Leibniz-Zentrum fuer Informatik

CY - Dagstuhl, Germany

ER -

King's College London - Homepage

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