King's College London

Research portal

Computing the Antiperiod(s) of a String

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

Standard

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

30th Annual Symposium on Combinatorial Pattern Matching, CPM 2019. ed. / Nadia Pisanti; Solon P. Pissis. Vol. 128 Dagstuhl, Germany : Schloss Dagstuhl--Leibniz-Zentrum fuer Informatik, 2019. 32.

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

Harvard

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

APA

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

Vancouver

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

Author

Alamro, Hayam Mohammed A ; Badkobeh, Golnaz ; Belazzougui, Djamal ; Iliopoulos, Costas ; Puglisi, Simon J. / Computing the Antiperiod(s) of a String. 30th Annual Symposium on Combinatorial Pattern Matching, CPM 2019. editor / Nadia Pisanti ; Solon P. Pissis. Vol. 128 Dagstuhl, Germany : Schloss Dagstuhl--Leibniz-Zentrum fuer Informatik, 2019.

Bibtex Download

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

}

RIS (suitable for import to EndNote) Download

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 -

View graph of relations

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