2026-07-25T13:23:51Z https://drops.dagstuhl.de/oai

oai:drops-oai.dagstuhl.de:12750 2024-03-06T10:50:44Z ddc:004 open_access

Palindromic k-Factorization in Pure Linear Time Rubinchik, Mikhail Shur, Arseny M. stringology palindrome palindromic factorization online algorithm Given a string s of length n over a general alphabet and an integer k, the problem is to decide whether s is a concatenation of k nonempty palindromes. Two previously known solutions for this problem work in time O(kn) and O(nlog n) respectively. Here we settle the complexity of this problem in the word-RAM model, presenting an O(n)-time online deciding algorithm. The algorithm simultaneously finds the minimum odd number of factors and the minimum even number of factors in a factorization of a string into nonempty palindromes. We also demonstrate how to get an explicit factorization of s into k palindromes with an O(n)-time offline postprocessing. Schloss Dagstuhl – Leibniz-Zentrum für Informatik Mikhail Rubinchik and Arseny M. Shur 2020 Is Part Of LIPIcs, Volume 170, 45th International Symposium on Mathematical Foundations of Computer Science (MFCS 2020) InProceedings Text doc-type:ResearchArticle publishedVersion application/pdf doi:10.4230/LIPIcs.MFCS.2020.81 urn:nbn:de:0030-drops-127508 https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.MFCS.2020.81 eng https://creativecommons.org/licenses/by/3.0/legalcode