2026-07-23T15:49:50Z https://drops.dagstuhl.de/oai

oai:drops-oai.dagstuhl.de:24917 2026-02-09T08:02:01Z ddc:004 open_access

Small Space Encoding and Recognition of k-Palindromic Prefixes Bathie, Gabriel Ellert, Jonas Starikovskaya, Tatiana palindromic length read-only algorithms palindromes Palindromes are non-empty strings that read the same forward and backward. We study the problem of recognizing so-called k-palindromic strings, which can be represented as the concatenation of exactly k palindromes. [Rubinchik and Shur, MFCS 2020] showed that the problem is solvable in linear space and time. We present a read-only algorithm that recognizes all k-palindromic prefixes of a string T of length n in O(n ⋅ 6^{k²} ⋅ log^k n) time and O(6^{k²} ⋅ log^k n) space. As a corollary, we also obtain a read-only algorithm for computing the palindromic length of T, i.e., the smallest k such that T is k-palindromic, in O(n ⋅ 6^{k²} ⋅ log^⌈k/2⌉ n) time and O(6^{k²} ⋅ log^⌈k/2⌉ n) space. Schloss Dagstuhl – Leibniz-Zentrum für Informatik Gabriel Bathie and Jonas Ellert and Tatiana Starikovskaya 2025 Is Part Of LIPIcs, Volume 359, 36th International Symposium on Algorithms and Computation (ISAAC 2025) InProceedings Text doc-type:ResearchArticle publishedVersion application/pdf doi:10.4230/LIPIcs.ISAAC.2025.9 urn:nbn:de:0030-drops-249178 https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.ISAAC.2025.9 eng https://creativecommons.org/licenses/by/4.0/legalcode