2026-08-25T15:33:46Z https://drops.dagstuhl.de/oai

oai:drops-oai.dagstuhl.de:27235 2026-08-25T13:18:19Z ddc:004 open_access

Online Approximate Circular Pattern Matching in Small Space Charalampopoulos, Panagiotis El Ghazi, Taha Ellert, Jonas Gawrychowski, Paweł Starikovskaya, Tatiana Small-space algorithms approximate pattern matching circular pattern matching In approximate circular pattern matching the goal is to compute all approximate occurrences of all rotations of a pattern P in a text T. We study this problem under the two most fundamental string distance metrics, the Hamming distance and the edit distance, in the setting where the text arrives online and the available space is limited. Specifically, we wish to report each ending position j of an approximate occurrence before symbol T[j+1] arrives, using sublinear space on top of having read-only access to P and (the seen prefix of) T. For both variants, we present algorithms that use O(poly(k)) extra space and process each arriving symbol in O(poly(k)) time. Notably, with an overhead, our algorithms can be lifted to the asymmetric streaming setting, where we only have read-only access to the pattern for free and account for all extra space. Schloss Dagstuhl – Leibniz-Zentrum für Informatik Panagiotis Charalampopoulos and Taha El Ghazi and Jonas Ellert and Paweł Gawrychowski and Tatiana Starikovskaya 2026 Is Part Of LIPIcs, Volume 388, 34th Annual European Symposium on Algorithms (ESA 2026) InProceedings Text doc-type:ResearchArticle publishedVersion application/pdf doi:10.4230/LIPIcs.ESA.2026.99 urn:nbn:de:0030-drops-272358 https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.ESA.2026.99 eng https://creativecommons.org/licenses/by/4.0/legalcode