2026-08-02T01:24:54Z https://drops.dagstuhl.de/oai

oai:drops-oai.dagstuhl.de:8506 2024-03-06T10:42:20Z ddc:004 open_access

String Periods in the Order-Preserving Model Gourdel, Garance Kociumaka, Tomasz Radoszewski, Jakub Rytter, Wojciech Shur, Arseny Walen, Tomasz order-preserving pattern matching period efficient algorithm The order-preserving model (op-model, in short) was introduced quite recently but has already attracted significant attention because of its applications in data analysis. We introduce several types of periods in this setting (op-periods). Then we give algorithms to compute these periods in time O(n), O(n log log n), O(n log^2 log n/log log log n), O(n log n) depending on the type of periodicity. In the most general variant the number of different periods can be as big as Omega(n^2), and a compact representation is needed. Our algorithms require novel combinatorial insight into the properties of such periods. Schloss Dagstuhl – Leibniz-Zentrum für Informatik Garance Gourdel and Tomasz Kociumaka and Jakub Radoszewski and Wojciech Rytter and Arseny Shur and Tomasz Walen 2018 Is Part Of LIPIcs, Volume 96, 35th Symposium on Theoretical Aspects of Computer Science (STACS 2018) InProceedings Text doc-type:ResearchArticle publishedVersion application/pdf doi:10.4230/LIPIcs.STACS.2018.38 urn:nbn:de:0030-drops-85064 https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.STACS.2018.38 eng https://creativecommons.org/licenses/by/3.0/legalcode