pith. sign in

arxiv: 1906.09732 · v1 · pith:6HSB36AYnew · submitted 2019-06-24 · 💻 cs.DS

Dynamic Palindrome Detection

Amihood Amir , Itai Boneh This is my paper

Pith reviewed 2026-05-25 17:24 UTC · model grok-4.3

classification 💻 cs.DS
keywords dynamic stringspalindromeslongest palindromedata structurespolylogarithmic timesymbol editsstring algorithmsdynamic string matching
0
0 comments X

The pith

The longest palindrome substring can be maintained in polylogarithmic time per symbol edit.

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

This paper examines the classic problem of finding the longest palindromic substring but in a dynamic setting where the string undergoes repeated symbol edits. It shows that a data structure can keep track of the current longest palindrome and update it after each edit in only poly-logarithmic time. A reader would care because many real-world strings, such as documents or biological sequences, change over time and prior dynamic string results had focused mainly on longest common factors. The work places palindrome maintenance on similar footing to other dynamic string tasks. This means algorithms that rely on finding long palindromes can now operate efficiently even when the input keeps changing.

Core claim

The paper shows that the longest palindrome can be maintained in poly-logarithmic time per symbol edit by building on existing dynamic string data structures that support the necessary updates and queries under the standard word-RAM model.

What carries the argument

Dynamic string data structure supporting polylog-time updates and palindrome-related queries after symbol edits.

If this is right

  • Dynamic versions of other palindrome-related problems become solvable in polylog time per edit.
  • Real-time applications that monitor changing text for palindromes can run efficiently without full recomputation.
  • The technique integrates with prior dynamic longest-common-factor results to handle multiple string properties at once.
  • Algorithms in areas such as pattern matching or compression that depend on palindromes can now handle evolving inputs.

Where Pith is reading between the lines

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

  • Similar polylog maintenance might extend to finding the longest palindromic substring with a bounded number of mismatches.
  • The approach could be tested by implementing it on large evolving strings and measuring actual update times against naive recomputation.
  • Connections may exist to dynamic problems in computational biology where sequences mutate one base at a time.

Load-bearing premise

A dynamic string data structure already exists that can answer the needed palindrome queries and perform updates in polylog time.

What would settle it

A concrete sequence of symbol edits on a string where any data structure requires super-polylogarithmic time per edit to correctly report the new longest palindrome.

read the original abstract

Lately, there is a growing interest in dynamic string matching problems. Specifically, the dynamic Longest Common Factor problem has been researched and some interesting results has been reached. In this paper we examine another classic string problem in a dynamic setting - finding the longest palindrome substring of a given string. We show that the longest palindrome can be maintained in poly-logarithmic time per symbol edit.

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

1 major / 1 minor

Summary. The manuscript examines the dynamic longest palindromic substring problem under symbol edits. Building on recent work in dynamic string matching (e.g., dynamic LCF), it claims that the longest palindrome substring can be maintained in polylogarithmic time per update.

Significance. If the claimed data structure and update procedure exist and achieve the stated bound under the word-RAM model, the result would extend the toolkit of dynamic string algorithms and could be useful in applications requiring frequent palindrome queries on mutable text.

major comments (1)
  1. [Abstract] Abstract: the central claim that the longest palindrome 'can be maintained in poly-logarithmic time per symbol edit' is stated without any proof sketch, data-structure description, reduction to dynamic LCF, or time-bound derivation; this absence makes the soundness of the result impossible to evaluate from the supplied text.
minor comments (1)
  1. [Abstract] Abstract: 'some interesting results has been reached' contains a subject-verb agreement error and should read 'have been reached'.

Simulated Author's Rebuttal

1 responses · 0 unresolved

We thank the referee for their review of the manuscript. We address the single major comment below.

read point-by-point responses

  1. Referee: [Abstract] Abstract: the central claim that the longest palindrome 'can be maintained in poly-logarithmic time per symbol edit' is stated without any proof sketch, data-structure description, reduction to dynamic LCF, or time-bound derivation; this absence makes the soundness of the result impossible to evaluate from the supplied text.

    Authors: We agree that the abstract states the main claim without elaboration on the approach. The manuscript reduces the dynamic longest palindromic substring problem to the dynamic longest common factor problem (as referenced in the referee summary), which yields the stated polylogarithmic update time under the word-RAM model. In the revised version we will expand the abstract to include a concise outline of this reduction and the resulting time bound derivation. revision: yes

Circularity Check

0 steps flagged

No significant circularity

full rationale

The paper states a positive algorithmic result: longest-palindrome maintenance under symbol edits in polylog time per update, situated within prior dynamic string-matching literature. The provided abstract and claim contain no equations, no self-referential definitions, no fitted parameters renamed as predictions, and no load-bearing self-citations. The derivation chain is not exhibited in the text; the result is presented as a direct algorithmic contribution rather than a reduction to its own inputs. This is the normal non-circular outcome for an algorithmic paper whose central claim does not reduce by construction.

Axiom & Free-Parameter Ledger

0 free parameters · 0 axioms · 0 invented entities

Abstract supplies no information on free parameters, axioms, or invented entities.

pith-pipeline@v0.9.0 · 5567 in / 848 out tokens · 26868 ms · 2026-05-25T17:24:47.778538+00:00 · methodology

discussion (0)

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

Forward citations

Cited by 1 Pith paper

Reviewed papers in the Pith corpus that reference this work. Sorted by Pith novelty score.

  1. Dynamic Longest Common Substring in Polylogarithmic Time

    cs.DS 2020-06 conditional novelty 8.0

    Dynamic LCS maintained under edits in amortized O(log^7 n) time whp, with Omega(log n / log log n) lower bound.

Reference graph

Works this paper leans on

25 extracted references · 25 canonical work pages · cited by 1 Pith paper · 1 internal anchor

  1. [1]

    Amir and I

    A. Amir and I. Boneh. Locally maximal common factors as a tool for efficient dynamic string algorithms. In Proc. 29st Annual Symposium on Combinatorial Pattern Matching (CPM) , LIPICS, pages 11:1–11:13, 2018

    work page 2018

  2. [2]

    A. Amir, P. Charalampopoulos, C.S. Iliopoulos, S.P. Pissis, and J. Ra- doszewski. Longest common factor after one edit operation. In Proc. 24th International Symposium on String Processing and Information Retrieval (SPIRE), LNCS, pages 14–26. Springer, 2017

    work page 2017

  3. [3]

    A. Amir, P. Charalampopoulos, S. P. Pissis, and J. Radoszewski. Longest common factor made fully dynamic. Technical Report abs/1804.08731, CoRR, April 2018

    work page internal anchor Pith review Pith/arXiv arXiv 2018

  4. [4]

    Amir and M

    A. Amir and M. Farach. Adaptive dictionary matching. Proc. 32nd IEEE FOCS, pages 760–766, 1991

    work page 1991

  5. [5]

    A. Amir, M. Farach, R.M. Idury, J.A. La Poutr´ e, and A.A Sch¨ affer. Improved dynamic dictionary matching. Information and Computation , 119(2):258–282, 1995

    work page 1995

  6. [6]

    Amir and E

    A. Amir and E. Kondratovsky. Searching for a modified pattern in a chang- ing text. In Proc. 25th International Symposium on String Processing and Information Retrieval (SPIRE) , LNCS, pages 241–253. Springer, 2018

    work page 2018

  7. [7]

    Amir, G.M

    A. Amir, G.M. Landau, M. Lewenstein, and D. Sokol. Dynamic text and static pattern matching. ACM Transactions on Algorithms , 3(2), 2007

    work page 2007

  8. [8]

    Amir and B

    A. Amir and B. Porat. Approximate on-line palindrome recognition, and applications. In Proc. 25th Annual Symposium on Combinatorial Pattern Matching (CPM), pages 21–29, 2014

    work page 2014

  9. [9]

    Apostolico, D

    A. Apostolico, D. Breslauer, and Z. Galil. Optimal parallel algorithms for periods, palindromes and squares. In Proc. 19th International Collo- quium on Automata, Languages, and Programming (ICALP) , volume 623 of LNCS, pages 296–307. Springer, 1992

    work page 1992

  10. [10]

    Bille, A

    P. Bille, A. R. Christiansen, P. H. Cording, I. L. Gørtz, F. R. Skjoldjensen, H. W. Vildhøj, and S. Vind. Dynamic relative compression, dynamic partial sums, and substring concatenation. Algorithmica, 16(4):464–497, 2017

    work page 2017

  11. [11]

    Crochemore, C

    M. Crochemore, C. Hancart, and T. Lecroq. Algorithms on Strings . Cam- bridge University Press, 2007

    work page 2007

  12. [12]

    Demetrescu, D

    C. Demetrescu, D. Eppstein, Z. Galil, and G. Italiano. Algorithms and theory of computation handbook. chapter Dynamic Graph Algorithms, pages 9–9. Chapman & Hall/CRC, 2010. 16

    work page 2010

  13. [13]

    Fuglsang

    A. Fuglsang. Distribution of potential type ii restriction sites (palindromes) in prokaryotes. Biochemical and Biophysical Research Communications , 310(2):280–285, 2003

    work page 2003

  14. [14]

    Z. Galil. On converting on-line algorithms into real-time and on real-time algorithms for string matching and palindrome recognition.SIGACT News, pages 26–30, Nov.-Dec. 1975

    work page 1975

  15. [15]

    Gelfand and E.V

    M.S. Gelfand and E.V. Koonin. Avoidance of palindromic words in bacterial and archaeal genomes: a close connection with restriction enzymes. Nucleic Acids Res, 25:2430–2439, 1997

    work page 1997

  16. [16]

    M. Gu, M. Farach, and R. Beigel. An efficient algorithm for dynamic text indexing. Proc. 5th Annual ACM-SIAM Symposium on Discrete Al- gorithms, pages 697–704, 1994

    work page 1994

  17. [17]

    Idury and A.A Sch¨ affer

    R.M. Idury and A.A Sch¨ affer. Dynamic dictionary matching with failure functions. Proc. 3rd Annual Symposium on Combinatorial Pattern Match- ing, pages 273–284, 1992

    work page 1992

  18. [18]

    Karp and M.O

    R.M. Karp and M.O. Rabin. Efficient randomized pattern-matching algo- rithms. IBM Journal of Res. and Dev. , pages 249–260, 1987

    work page 1987

  19. [19]

    Lisnic, I.K

    B. Lisnic, I.K. Svetec, H. Saric, I. Nikolic, and Z. Zgaga. Palindrome content of the yeast Saccharomyces cerevisiae genome. Curr Genetics, 47:289–297, 2005

    work page 2005

  20. [20]

    W. Maass. Quadratic lower bounds for deterministic and nondeterministic one-tape turing machines (extended abstract). In Proc. 16th Annual ACM Symposium on the Theory of Computing (STOC) , pages 401–408, 1984

    work page 1984

  21. [21]

    Manacher

    G. Manacher. A new linear-time “on-line” algorithm for finding the smallest initial palindrome of a string. Journal of the ACM , 22(3):346–351, 1975

    work page 1975

  22. [22]

    Mehlhorn, R

    K. Mehlhorn, R. Sundar, and C. Uhrig. Maintaining dynamic sequences under equality-tests in polylogarithmic time. In Proc. 5th ACM-SIAM Symposium on Discrete Algorithms (SODA) , pages 213–222, 1994

    work page 1994

  23. [23]

    S. C. Sahinalp and U. Vishkin. Efficient approximate and dynamic match- ing of patterns using a labeling paradigm. Proc. 37th FOCS, pages 320–328, 1996

    work page 1996

  24. [24]

    Slisenko

    A.O. Slisenko. Recognition of palindromes by multihead turing machines. In Proc. of the Steklov Math. Inst. , volume 129, pages 30–202. Acad. of Sciences of the USSR, 1973

    work page 1973

  25. [25]

    S. K. Srivastava and H.S. Robins. Palindromic nucleotide analysis in human t cell receptor rearrangements. PLOS one, 7(12):e52250, 2012. 17

    work page 2012