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

https://hal.inria.fr/hal-02336623
Contributor : Marie-France Sagot <>
Submitted on : Tuesday, October 29, 2019 - 8:43:29 AM
Last modification on : Monday, October 19, 2020 - 8:26:03 PM
Long-term archiving on: : Thursday, January 30, 2020 - 1:31:20 PM

File

Online_Antiperiod_Array.pdf
Files produced by the author(s)

Identifiers

Citation

Mai Alzamel, Alessio Conte, Daniele Greco, Veronica Guerrini, Costas 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⟩

Share

Metrics

Record views

69

Files downloads

251