Abstract:Palindromes are strings that read the same forward and backward. The computation of palindromic structures within strings is a fundamental problem in string algorithms, being motivated by potential applications in formal language theory and bioinformatics. Although the number of palindromic factors in a string of length $n$ can be quadratic, they can be implicitly represented in $O(n \log n)$ bits of space by storing the lengths of all maximal palindromes in an integer array, which can be computed in $O(n)$ time~[Manacher, 1975]. In this paper, for any positive constant $\epsilon < 1$, we propose a novel $(3(1+\epsilon)n + o(n))$-bit representation of all maximal palindromes in a string, which enables $O(1)$-time retrieval of the length of the maximal palindrome centered at any given position. The data structure can be constructed in $O(n)$ time and $O(n)$-bit working space from the input string of length $n$. Since Manacher's algorithm and the notion of maximal palindromes are widely utilized for solving numerous problems involving palindromic structures, our compact representation will accelerate the development of more space-efficient solutions to such problems. Indeed, as the first application of our compact representation of maximal palindromes, we present a data structure of size $O(n)$ bits that can compute the longest palindrome appearing in any given factor of a string of length $n$ in $O(\log n)$ time.
From: Takuya Mieno [view email]
[v1]
Wed, 20 Aug 2025 03:24:54 UTC (179 KB)
[v2]
Tue, 23 Dec 2025 10:45:28 UTC (192 KB)
[v3]
Thu, 14 May 2026 02:31:16 UTC (193 KB)
[v4]
Mon, 6 Jul 2026 08:42:42 UTC (195 KB)
此内容由惯性聚合(RSS阅读器)自动聚合整理，仅供阅读参考。 原文来自 — 版权归原作者所有。