2026-08-11T21:21:20Z https://drops.dagstuhl.de/oai

oai:drops-oai.dagstuhl.de:7591 2024-03-06T10:40:41Z ddc:004 open_access

Streaming Periodicity with Mismatches Ergün, Funda Grigorescu, Elena Sadeqi Azer, Erfan Zhou, Samson String algorithms Streaming algorithms Pattern matching Randomized algorithms Sublinear algorithms We study the problem of finding all k-periods of a length-n string S, presented as a data stream. S is said to have k-period p if its prefix of length n-p differs from its suffix of length n-p in at most k locations. We give a one-pass streaming algorithm that computes the k-periods of a string S using poly(k, log n) bits of space, for k-periods of length at most n/2. We also present a two-pass streaming algorithm that computes k-periods of S using poly(k, log n) bits of space, regardless of period length. We complement these results with comparable lower bounds. Schloss Dagstuhl – Leibniz-Zentrum für Informatik Funda Ergün and Elena Grigorescu and Erfan Sadeqi Azer and Samson Zhou 2017 Is Part Of LIPIcs, Volume 81, Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques (APPROX/RANDOM 2017) InProceedings Text doc-type:ResearchArticle publishedVersion application/pdf doi:10.4230/LIPIcs.APPROX-RANDOM.2017.42 urn:nbn:de:0030-drops-75911 https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.APPROX-RANDOM.2017.42 eng https://creativecommons.org/licenses/by/3.0/legalcode