2024/10/04 by Gabriel Bathie, Bathie, Gabriel, Jonas Ellert +3
Biochemistry, Genetics and Molecular Biology · Computer Science · #Algorithms and Data Compression #DNA and Biological Computing #Data Structures and Algorithms (cs.DS) #FOS: Computer and information sciences #semigroups and automata theory
paper · pdf · doi:10.48550/arxiv.2410.03309
openalex publication_date 2024/10/04 · openalex created_date 2025/10/10 · openalex updated_date 2026/07/28
Palindromes are non-empty strings that read the same forward and backward. The problem of recognizing strings that can be represented as the concatenation of even-length palindromes, the concatenation of palindromes of length at least two, and the concatenation of exactly k palindromes was introduced in the seminal paper of Knuth, Morris, and Pratt [SIAM J. Comput., 1977]. In this work, we study the problem of recognizing so-called k-palindromic strings, which can be represented as the concatenation of exactly k palindromes. We show the following results: 1. First, we show a structural characterization of the set of all k-palindromic prefixes of a string by representing it as a union of a small number of highly structured string sets, called affine prefix sets. Representing the lengths of the k-palindromic prefixes in this way requires O(6k2 ⋅ logk n) space. By constructing a lower bound, we show that the space complexity is optimal up to polylogarithmic factors for reasonably small values of k. 2. Secondly, we derive a read-only algorithm that, given a string T of length n and an integer k, computes a compact representation of i-palindromic prefixes of T, for all 1 ≤ i ≤ k. The algorithm uses O(n ⋅ 6k2 ⋅ logk n) time and O(6k2 ⋅ logk n) space. 3. Finally, we also give a read-only algorithm for computing the palindromic length of T, which is the smallest ℓ such that T is ℓ-palindromic. Here, we achieve O(n ⋅ 6ℓ2 ⋅ log^\lceilℓ/2 \rceil n) time and O(6ℓ2 ⋅ log^\lceilℓ/2\rceil n) space. For some values of ℓ, this is the first algorithm for palindromic length that uses o(n) additional working space on top of the input.