Service interruption on Monday 11 July from 12:30 to 13:00: all the sites of the CCSD (HAL, Epiciences, SciencesConf, AureHAL) will be inaccessible (network hardware connection).
Skip to Main content Skip to Navigation
Conference papers

Online Algorithms on Antipowers and Antiperiods

Abstract : The definition of antipower introduced by Fici et al. (ICALP 2016) captures the notion of being the opposite of a power : a sequence of k pairwise distinct blocks of the same length. Recently, Alamro et al. (CPM 2019) defined a string to have an antiperiod if it is a prefix of an antipower, and gave complexity bounds for the offline computation of the minimum antiperiod and all the antiperiods of a word. In this paper, we address the same problems in the online setting. Our solutions rely on new arrays that compactly and incrementally store antiperiods and antipowers as the word grows, obtaining in the process this information for all the word's prefixes. We show how to compute those arrays online in O(n log n) space, O(n log n) time, and o(n) delay per character, for any constant > 0. Running times are worst-case and hold with high probability. We also discuss more space-efficient solutions returning the correct result with high probability, and small data structures to support random access to those arrays.
Document type :
Conference papers
Complete list of metadata

Cited literature [30 references]  Display  Hide  Download
Contributor : Marie-France Sagot Connect in order to contact the contributor
Submitted on : Tuesday, October 29, 2019 - 8:43:29 AM
Last modification on : Thursday, January 6, 2022 - 5:30:02 PM
Long-term archiving on: : Thursday, January 30, 2020 - 1:31:20 PM


Files produced by the author(s)



Mai Alzamel, Alessio Conte, Daniele Greco, Veronica Guerrini, Costas S. Iliopoulos, et al.. Online Algorithms on Antipowers and Antiperiods. Symposium on String Processing and Information Retrieval (SPIRE), 2019, Segovia, Spain. pp.175-188, ⟨10.1007/978-3-030-32686-9_13⟩. ⟨hal-02336623⟩



Record views


Files downloads