pith. sign in

arxiv: 2508.14384 · v3 · pith:GDGML2N2new · submitted 2025-08-20 · 💻 cs.DS

Almost succinct representation of maximal palindromes

Takuya Mieno , Tomohiro I This is my paper

Pith reviewed 2026-05-18 22:44 UTC · model grok-4.3

classification 💻 cs.DS
keywords maximal palindromessuccinct data structuresstring algorithmspalindrome computationspace-efficient representationsManacher's algorithmlongest palindromic factors
0
0 comments X

The pith

All maximal palindromes in a string fit in 3(1+ε)n + o(n) bits with O(1) retrieval of any center length.

A machine-rendered reading of the paper's core claim, the machinery that carries it, and where it could break.

The paper develops a compact way to represent every maximal palindrome without storing their full lengths explicitly in an array. The structure answers the length at any chosen center position instantly while using only a small multiple of n bits overall. It builds directly from the input string in linear time. This improves on the O(n log n) bits required by a plain array of lengths. The same representation yields an O(n)-bit structure that finds the longest palindrome inside any given substring in logarithmic time.

Core claim

For any positive constant ε < 1, a (3(1+ε)n + o(n))-bit representation of all maximal palindromes exists that supports O(1)-time retrieval of the length of the maximal palindrome centered at any given position and can be constructed in O(n) time from a string of length n.

What carries the argument

A compressed encoding of the array of maximal palindrome lengths that supports constant-time direct access to any entry.

If this is right

  • Existing algorithms that rely on Manacher's algorithm or maximal palindromes can be made more space-efficient by swapping in this representation.
  • An O(n)-bit auxiliary structure computes the longest palindrome inside any factor of the string in O(log n) time.
  • Problems in formal language theory and bioinformatics that process palindromic factors gain a smaller memory footprint.
  • Any solution that previously stored an explicit array of palindrome lengths now has a drop-in replacement using nearly three bits per character.

Where Pith is reading between the lines

These are editorial extensions of the paper, not claims the author makes directly.

  • The representation can be combined with other succinct string indexes to handle palindromes inside compressed or repetitive texts.
  • Similar compression ideas might apply to other linear-time string structures such as runs or Lyndon factors.
  • The O(log n) query for longest palindromes in factors suggests a path toward even faster or fully constant-time variants if additional space is allowed.

Load-bearing premise

Characters of the input string can be read and compared in constant time under the standard word-RAM model with word size logarithmic in n.

What would settle it

A concrete string of length n for which any encoding that answers center lengths in O(1) time requires more than 3(1+ε)n + o(n) bits.

Figures

Figures reproduced from arXiv: 2508.14384 by Takuya Mieno, Tomohiro I.

Figure 1
Figure 1. Figure 1: Encodings of two strings, abccbabbaa and bcaacbaabb. Non-empty maximal even-palindromes are indicated as double-headed arrows. For each string, LEPal array, its corresponding centers, the differences between adjacent centers, and the binary encoding are shown. The binary encoding represents the differences in unary. For the simplicity of the discussions below, we assume that n is a multiple of 2τ where τ i… view at source ↗
Figure 2
Figure 2. Figure 2: Illustration of a part of an input string and maximal even-palindromes within [PITH_FULL_IMAGE:figures/full_fig_p007_2.png] view at source ↗
Figure 3
Figure 3. Figure 3: Illustration for a contradiction in the case where [PITH_FULL_IMAGE:figures/full_fig_p014_3.png] view at source ↗
read the original 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 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.

Editorial analysis

A structured set of objections, weighed in public.

Desk editor's note, referee report, simulated authors' rebuttal, and a circularity audit. Tearing a paper down is the easy half of reading it; the pith above is the substance, this is the friction.

Referee Report

2 major / 2 minor

Summary. The manuscript proposes a novel almost-succinct data structure for representing all maximal palindromes in a string of length n. Specifically, for any positive constant ε < 1, it achieves a space complexity of 3(1+ε)n + o(n) bits, supports O(1)-time queries for the length of the maximal palindrome centered at any position, and can be constructed in O(n) time. Additionally, it presents an application yielding an O(n)-bit data structure for computing the longest palindrome in any given factor of the string in O(log n) time.

Significance. If the claims hold, the result improves upon the O(n log n)-bit Manacher array by providing a nearly linear-space encoding of maximal palindromes while preserving linear construction and constant-time center-length queries. This is a meaningful advance for space-efficient string algorithms, especially in bioinformatics applications that rely on palindromic structures. The O(n)-bit factor-query structure is a useful demonstration of the representation's utility. The work correctly operates under standard word-RAM assumptions with Θ(log n)-bit words.

major comments (2)
  1. [§4] §4, construction of the radii encoding: the claim that the representation uses exactly 3(1+ε) bits per position plus o(n) must be accompanied by an explicit accounting of how the ε-dependent compression (e.g., via block encoding or sampling) produces the o(n) overhead without increasing the O(1) query time; the current sketch leaves the dependence on ε unclear.
  2. [Theorem 5] Theorem 5 (factor-query application): the O(log n) query for the longest palindrome inside an arbitrary factor is reduced to O(1) center-length probes plus additional structures; the space analysis for these auxiliary structures must be shown to remain O(n) bits overall, as the reduction appears to add logarithmic factors that could affect the stated bound.
minor comments (2)
  1. [Abstract] Abstract: the parenthetical '(3(1+ε)n + o(n))' should be written with consistent spacing and parentheses for readability.
  2. [Preliminaries] Preliminaries: the definition of maximal palindromes could include a short example illustrating odd- and even-length cases to aid readers unfamiliar with Manacher's algorithm.

Simulated Author's Rebuttal

2 responses · 0 unresolved

We thank the referee for the careful reading, positive assessment, and recommendation for minor revision. The comments help clarify key aspects of the construction and application, and we will incorporate the requested details in the revised manuscript.

read point-by-point responses

  1. Referee: [§4] §4, construction of the radii encoding: the claim that the representation uses exactly 3(1+ε) bits per position plus o(n) must be accompanied by an explicit accounting of how the ε-dependent compression (e.g., via block encoding or sampling) produces the o(n) overhead without increasing the O(1) query time; the current sketch leaves the dependence on ε unclear.

    Authors: We agree that the sketch in Section 4 would benefit from a more explicit space and time analysis. In the revised manuscript we will expand the description of the radii encoding to include a formal breakdown: positions are partitioned into blocks whose size is a function of ε; the majority of small radii are encoded using a fixed 3-bit representation per position within each block; larger radii are handled via ε-dependent sampling at intervals of size Θ(1/ε), with block summaries stored explicitly. The sampling overhead is o(n) for any fixed ε > 0, and constant-time queries are preserved by accessing a constant number of samples plus a bounded-size block scan. We will add a supporting lemma that makes the dependence on ε fully explicit while confirming that construction remains O(n) and queries remain O(1). revision: yes

  2. Referee: [Theorem 5] Theorem 5 (factor-query application): the O(log n) query for the longest palindrome inside an arbitrary factor is reduced to O(1) center-length probes plus additional structures; the space analysis for these auxiliary structures must be shown to remain O(n) bits overall, as the reduction appears to add logarithmic factors that could affect the stated bound.

    Authors: We appreciate the referee highlighting the need for a precise space accounting in the proof of Theorem 5. The auxiliary structures consist of a succinct range-maximum-query structure (O(n) bits) over the maximal-palindrome-length array together with a small number of additional succinct arrays for center location; these are realized with standard O(n)-bit representations that incur no extra logarithmic space factor. The O(log n) query time stems from a binary search over candidate centers or lengths inside the queried factor, each probe using an O(1)-time access to the main representation. In the revision we will augment the proof with an explicit space summation showing that the total auxiliary space is O(n) bits and does not exceed the claimed bound when combined with the (3(1+ε)n + o(n))-bit main structure. revision: yes

Circularity Check

0 steps flagged

No significant circularity detected in derivation chain

full rationale

The paper derives its (3(1+ε)n + o(n))-bit representation and O(1) query time via an explicit encoding of the Manacher radii array using standard succinct structures (e.g., bit vectors and rank/select) with a tunable ε redundancy parameter. This construction is independent of the claimed bounds: the space is obtained by partitioning the radii into blocks and applying known o(n)-bit overhead techniques, while O(n) preprocessing follows directly from Manacher's linear-time algorithm plus constant-time word-RAM operations. No equation or claim reduces to a fitted parameter, self-definition, or self-citation chain; the central result is a concrete data structure whose correctness and complexity are established against external benchmarks (Manacher 1975 and standard succinct dictionary results) without circular reduction to the output itself.

Axiom & Free-Parameter Ledger

0 free parameters · 1 axioms · 0 invented entities

The paper relies on the standard word-RAM model for its time and space claims; no free parameters, invented entities, or non-standard axioms are stated in the abstract.

axioms (1)
  • domain assumption Word-RAM model with word size Θ(log n) bits and constant-time character access/comparison.
    Required for the stated O(n) construction time and O(1) query time.

pith-pipeline@v0.9.0 · 5791 in / 1426 out tokens · 52460 ms · 2026-05-18T22:44:18.511621+00:00 · methodology

discussion (0)

Sign in with ORCID, Apple, or X to comment. Anyone can read and Pith papers without signing in.

Lean theorems connected to this paper

Citations machine-checked in the Pith Canon. Every link opens the source theorem in the public Lean library.

What do these tags mean?
matches
The paper's claim is directly supported by a theorem in the formal canon.
supports
The theorem supports part of the paper's argument, but the paper may add assumptions or extra steps.
extends
The paper goes beyond the formal theorem; the theorem is a base layer rather than the whole result.
uses
The paper appears to rely on the theorem as machinery.
contradicts
The paper's claim conflicts with a theorem or certificate in the canon.
unclear
Pith found a possible connection, but the passage is too broad, indirect, or ambiguous to say the theorem truly supports the claim.

Reference graph

Works this paper leans on

28 extracted references · 28 canonical work pages

  1. [1]

    Pissis, and Jakub Ra- doszewski

    Amihood Amir, Panagiotis Charalampopoulos, Solon P. Pissis, and Jakub Ra- doszewski. Dynamic and internal longest common substring. Algorithmica, 82(12):3707–3743, 2020

    work page 2020

  2. [2]

    Paralleldetectionofallpalindromes in a string.Theor

    AlbertoApostolico, DanyBreslauer, andZviGalil. Paralleldetectionofallpalindromes in a string.Theor. Comput. Sci., 141(1&2):163–173, 1995

    work page 1995

  3. [3]

    Pissis, and Jakub Radoszewski

    Panagiotis Charalampopoulos, Solon P. Pissis, and Jakub Radoszewski. Longest palin- dromic substring in sublinear time. In33rd Annual Symposium on Combinatorial Pat- tern Matching, CPM 2022, June 27-29, 2022, Prague, Czech Republic, volume 223 of LIPIcs, pages 20:1–20:9. Schloss Dagstuhl - Leibniz-Zentrum für Informatik, 2022

    work page 2022

  4. [4]

    Episturmian words and some constructions of de Luca and Rauzy.Theor

    Xavier Droubay, Jacques Justin, and Giuseppe Pirillo. Episturmian words and some constructions of de Luca and Rauzy.Theor. Comput. Sci., 255(1-2):539–553, 2001

    work page 2001

  5. [5]

    Minimal generators in optimal time

    Jonas Ellert, Pawel Gawrychowski, and Tatiana Starikovskaya. Minimal generators in optimal time. In36th Annual Symposium on Combinatorial Pattern Matching, CPM 2025, June 17-19, 2025, Milan, Italy, volume 331 ofLIPIcs, pages 14:1–14:19. Schloss Dagstuhl - Leibniz-Zentrum für Informatik, 2025

    work page 2025

  6. [6]

    Uniqueness theorems for periodic functions.Pro- ceedings of the American Mathematical Society, 16(1):109–114, 1965

    Nathan J Fine and Herbert S Wilf. Uniqueness theorems for periodic functions.Pro- ceedings of the American Mathematical Society, 16(1):109–114, 1965

    work page 1965

  7. [7]

    Space-efficient preprocessing schemes for range minimum queries on static arrays.SIAM J

    Johannes Fischer and Volker Heun. Space-efficient preprocessing schemes for range minimum queries on static arrays.SIAM J. Comput., 40(2):465–492, 2011. 10

    work page 2011

  8. [8]

    Computing longest palindromic substring after single-character or block-wise edits

    Mitsuru Funakoshi, Yuto Nakashima, Shunsuke Inenaga, Hideo Bannai, and Masayuki Takeda. Computing longest palindromic substring after single-character or block-wise edits. Theor. Comput. Sci., 859:116–133, 2021

    work page 2021

  9. [9]

    Seiferas

    Zvi Galil and Joel I. Seiferas. Recognizing certain repetitions and reversals within strings. In 17th Annual Symposium on Foundations of Computer Science, Houston, Texas, USA, 25-27 October 1976, pages 236–252. IEEE Computer Society, 1976

    work page 1976

  10. [10]

    Algorithms on Strings, Trees, and Sequences - Computer Science and Computational Biology

    Dan Gusfield. Algorithms on Strings, Trees, and Sequences - Computer Science and Computational Biology. Cambridge University Press, 1997

    work page 1997

  11. [11]

    Palindrome pattern matching

    Tomohiro I, Shunsuke Inenaga, and Masayuki Takeda. Palindrome pattern matching. Theor. Comput. Sci., 483:162–170, 2013

    work page 2013

  12. [12]

    Palindromes compression and retrieval

    Michael Itzhaki. Palindromes compression and retrieval. InData Compression Con- ference, DCC 2025, Snowbird, UT, USA, March 18-21, 2025, page 375. IEEE, 2025

    work page 2025

  13. [13]

    Knuth, James H

    Donald E. Knuth, James H. Morris Jr., and Vaughan R. Pratt. Fast pattern matching in strings. SIAM J. Comput., 6(2):323–350, 1977

    work page 1977

  14. [14]

    Searching for gapped palindromes.Theor

    Roman Kolpakov and Gregory Kucherov. Searching for gapped palindromes.Theor. Comput. Sci., 410(51):5365–5373, 2009

    work page 2009

  15. [15]

    Dmitry Kosolobov, Mikhail Rubinchik, and Arseny M. Shur. Palk is linear recognizable online. In SOFSEM 2015: Theory and Practice of Computer Science - 41st Interna- tional Conference on Current Trends in Theory and Practice of Computer Science, Pec pod Sněžkou, Czech Republic, January 24-29, 2015. Proceedings, volume 8939 of Lecture Notes in Computer Scie...

    work page 2015

  16. [16]

    A quasilinear-time algorithm for tiling the plane isohedrally with a polyomino

    Stefan Langerman and Andrew Winslow. A quasilinear-time algorithm for tiling the plane isohedrally with a polyomino. In 32nd International Symposium on Compu- tational Geometry, SoCG 2016, June 14-18, 2016, Boston, MA, USA, volume 51 of LIPIcs, pages 50:1–50:15. Schloss Dagstuhl - Leibniz-Zentrum für Informatik, 2016

    work page 2016

  17. [17]

    Tomescu.Genome- Scale Algorithm Design: Bioinformatics in the Era of High-Throughput Sequencing (2nd edition)

    Veli Mäkinen, Djamal Belazzougui, Fabio Cunial, and Alexandru I. Tomescu.Genome- Scale Algorithm Design: Bioinformatics in the Era of High-Throughput Sequencing (2nd edition). Cambridge University Press, 2023

    work page 2023

  18. [18]

    Manacher

    Glenn K. Manacher. A new linear-time "on-line" algorithm for finding the smallest initial palindrome of a string.J. ACM, 22(3):346–351, 1975

    work page 1975

  19. [19]

    Efficient algorithms to compute compressed longest common substrings and compressed palindromes.Theor

    Wataru Matsubara, Shunsuke Inenaga, Akira Ishino, Ayumi Shinohara, Tomoyuki Nakamura, and Kazuo Hashimoto. Efficient algorithms to compute compressed longest common substrings and compressed palindromes.Theor. Comput. Sci., 410(8-10):900– 913, 2009. 11

    work page 2009

  20. [20]

    Data structures for computing unique palin- dromes in static and non-static strings.Algorithmica, 86(3):852–873, 2024

    Takuya Mieno and Mitsuru Funakoshi. Data structures for computing unique palin- dromes in static and non-static strings.Algorithmica, 86(3):852–873, 2024

    work page 2024

  21. [21]

    Computing palindromes on a trie in linear time

    Takuya Mieno, Mitsuru Funakoshi, and Shunsuke Inenaga. Computing palindromes on a trie in linear time. In33rd International Symposium on Algorithms and Computation, ISAAC 2022, December 19-21, 2022, Seoul, Korea, volume 248 ofLIPIcs, pages 15:1– 15:15. Schloss Dagstuhl - Leibniz-Zentrum für Informatik, 2022

    work page 2022

  22. [22]

    Finding top-k longest palindromes in substrings.Theor

    Kazuki Mitani, Takuya Mieno, Kazuhisa Seto, and Takashi Horiyama. Finding top-k longest palindromes in substrings.Theor. Comput. Sci., 979:114183, 2023

    work page 2023

  23. [23]

    Linear-time online algorithm for inferring the shortest path graph from a walk label

    Shintaro Narisada, Diptarama Hendrian, Ryo Yoshinaka, and Ayumi Shinohara. Linear-time online algorithm for inferring the shortest path graph from a walk label. Theor. Comput. Sci., 812:187–202, 2020

    work page 2020

  24. [24]

    Mikhail Rubinchik and Arseny M. Shur. Counting palindromes in substrings. InString Processing and Information Retrieval - 24th International Symposium, SPIRE 2017, Palermo, Italy, September 26-29, 2017, Proceedings, volume 10508 ofLecture Notes in Computer Science, pages 290–303. Springer, 2017

    work page 2017

  25. [25]

    Mikhail Rubinchik and Arseny M. Shur. EERTREE: an efficient data structure for processing palindromes in strings.Eur. J. Comb., 68:249–265, 2018

    work page 2018

  26. [26]

    Mikhail Rubinchik and Arseny M. Shur. Palindromic k-factorization in pure linear time. In 45th International Symposium on Mathematical Foundations of Computer Science, MFCS 2020, August 24-28, 2020, Prague, Czech Republic, volume 170 of LIPIcs, pages 81:1–81:14. Schloss Dagstuhl - Leibniz-Zentrum für Informatik, 2020

    work page 2020

  27. [27]

    PWS Publishing Company, 1997

    Michael Sipser.Introduction to the theory of computation. PWS Publishing Company, 1997

    work page 1997

  28. [28]

    Linear pattern matching algorithms

    Peter Weiner. Linear pattern matching algorithms. In 14th Annual Symposium on Switching and Automata Theory, Iowa City, Iowa, USA, October 15-17, 1973, pages 1–11. IEEE Computer Society, 1973. 12 A Appendix: proof of Lemma 3 This appendix provides a proof of Lemma 3. We state some known results, which will be used in the proof of Lemma 3. We say that ther...

    work page 1973