pith. sign in

arxiv: 2604.21140 · v1 · submitted 2026-04-22 · 💻 cs.DS

On Time-Memory Tradeoffs for Maximal Palindromes with Wildcards and k-Mismatches

Amihood Amir , Ayelet Butman , Michael Itzhaki , Dina Sokol This is my paper

Pith reviewed 2026-05-09 22:33 UTC · model grok-4.3

classification 💻 cs.DS
keywords maximal palindromeswildcardstime-memory tradeoffk-mismatchesstring algorithmsLCE queriesdon't care symbols
0
0 comments X

The pith

Applying wildcard-LCE techniques yields continuous time-memory tradeoffs for maximal palindromes with wildcards and k-mismatches.

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

The paper develops algorithms to identify all maximal palindromes in strings that contain wildcards, which match any character and break many standard string properties. It adapts existing wildcard longest-common-extension methods to support a continuous spectrum of time and space options, including the first non-trivial linear-space solution that improves the time-memory product in some parameter ranges. The same framework is extended to handle up to k mismatches, both with and without wildcards. A reader would care because palindromic structures appear in many string-processing tasks, and wildcards or mismatches model real-world uncertainty such as ambiguous symbols in data.

Core claim

By applying existing wildcard-LCE techniques, the authors obtain a continuous time-memory tradeoff for computing all maximal palindromes in a text with wildcards, including a non-trivial linear-space algorithm. The methods are generalized to the k-mismatches setting with or without wildcards, improving the best-known time-memory product in certain parameter ranges.

What carries the argument

Wildcard longest-common-extension (LCE) queries applied to palindrome-center detection and radius computation.

Load-bearing premise

Existing wildcard-LCE techniques can be applied directly to palindromes to produce the claimed continuous time-memory tradeoff and linear-space algorithm without hidden costs or restrictions.

What would settle it

A concrete input string containing wildcards on which the algorithm reports a different set of maximal palindromes than the exhaustive enumeration, or on which the achieved space-time product fails to meet the stated improvement.

Figures

Figures reproduced from arXiv: 2604.21140 by Amihood Amir, Ayelet Butman, Dina Sokol, Michael Itzhaki.

Figure 1
Figure 1. Figure 1: The counting and matching convolution between [PITH_FULL_IMAGE:figures/full_fig_p005_1.png] view at source ↗
Figure 2
Figure 2. Figure 2: Demonstration of the naive subroutines NaivePalFind and NaivePalExtend. The red dots are the centers provided as input to the respective subroutines. hence define the center of the interval P = [i . . j] to be cP := ⌊ i+j 2 ⌋. The assumption is valid because the transformation S ′ = S[1]$S[2]$ . . . $S[n] makes any subpalindrome in S into an odd-length subpalindrome in S ′ . We proceed to detail two naive … view at source ↗
Figure 3
Figure 3. Figure 3: Demonstration of the precise algorithm. At every step, we search for the longest [PITH_FULL_IMAGE:figures/full_fig_p010_3.png] view at source ↗
Figure 4
Figure 4. Figure 4: Demonstration of the approximation algorithm. At every step, we perform for each [PITH_FULL_IMAGE:figures/full_fig_p013_4.png] view at source ↗
read the original abstract

This paper addresses the problem of identifying palindromic factors in texts that include wildcards -- special characters that match all others. These symbols challenge many classical algorithms, as numerous combinatorial properties are not satisfied in their presence. We apply existing wildcard-LCE techniques to obtain a continuous time-memory tradeoff, and present the first non-trivial linear-space algorithm for computing all maximal palindromes with wildcards, improving the best known time-memory product in certain parameter ranges. Our main results are algorithms to find and approximate all maximal palindromes in a given text. We also generalize both methods to the $k$-mismatches setting, with or without wildcards.

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

0 major / 3 minor

Summary. The paper addresses computing all maximal palindromes (and their k-mismatch variants) in strings containing wildcards. It applies existing wildcard-LCE techniques to derive a continuous time-memory tradeoff and claims the first non-trivial linear-space algorithm, improving the time-memory product in certain parameter regimes. The results are generalized to the k-mismatches setting both with and without wildcards.

Significance. If the reduction from wildcard-LCE to maximal palindromes is correct and incurs no hidden asymptotic costs, the work supplies practical algorithmic improvements for a core string problem that arises in bioinformatics and pattern matching. The linear-space algorithm is a notable contribution for large inputs, and the continuous tradeoff fills a gap between prior discrete points. The paper explicitly builds on prior wildcard-LCE results rather than re-deriving them, which is a strength when the composition is verified.

minor comments (3)
  1. [Abstract] The abstract states that the linear-space algorithm is 'the first non-trivial' but does not quantify the improvement over the previous best time-memory product; a concrete comparison (e.g., O(n log n) time vs. prior O(n^{1.5})) would strengthen the claim.
  2. [Preliminaries] Notation for wildcard-LCE queries and palindrome centers is introduced without an explicit table of symbols; readers must infer the meaning of several subscripts from context in the technical sections.
  3. [Section 4] The generalization to k-mismatches is described at a high level; a short pseudocode block or explicit recurrence showing how the mismatch budget is propagated through the LCE calls would improve readability.

Simulated Author's Rebuttal

0 responses · 0 unresolved

We thank the referee for the positive and accurate summary of our work on maximal palindromes with wildcards and k-mismatches. We are pleased that the contributions—the continuous time-memory tradeoff via wildcard-LCE techniques and the first non-trivial linear-space algorithm—are recognized as filling a gap in the literature and improving the time-memory product in relevant regimes. The generalization to the k-mismatches setting is also noted. Given the recommendation for minor revision and the absence of any specific major comments, we have no points requiring rebuttal or revision at this time.

Circularity Check

0 steps flagged

No significant circularity detected

full rationale

The paper's derivation explicitly applies existing external wildcard-LCE techniques to derive continuous time-memory tradeoffs and the first non-trivial linear-space algorithm for maximal palindromes (with and without k-mismatches). No self-definitional reductions, fitted inputs renamed as predictions, or load-bearing self-citations appear in the abstract or described results; the claims rest on prior independent methods rather than internal tautologies or ansatzes smuggled via author overlap. The generalization steps are presented as direct extensions without reducing to the input data or definitions by construction.

Axiom & Free-Parameter Ledger

0 free parameters · 1 axioms · 0 invented entities

The central claims rest on standard string-algorithm assumptions and reuse of prior LCE methods; no new free parameters, axioms, or invented entities are introduced in the abstract.

axioms (1)
  • domain assumption Strings are finite sequences over a finite alphabet that includes a wildcard symbol matching any character
    Implicit foundation for all wildcard palindrome definitions and LCE usage.

pith-pipeline@v0.9.0 · 5416 in / 1127 out tokens · 25857 ms · 2026-05-09T22:33:10.265056+00:00 · methodology

discussion (0)

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

Reference graph

Works this paper leans on

40 extracted references · 37 canonical work pages

  1. [1]

    Abrahamson

    K. Abrahamson. Generalized string matching.SIAM Journal on Computing, 16(6):1039– 1051, 1987.doi:10.1137/0216067

    work page doi:10.1137/0216067 1987

  2. [2]

    Alzamel, C

    M. Alzamel, C. Hampson, C.S. Iliopoulos, Z. Lim, S. Pissis, D. Vlachakis, and S. Watts. Maximal degenerate palindromes with gaps and mismatches.Theoretical Computer Science, 978:114182, 2023.doi:10.1016/j.tcs.2023.114182

    work page doi:10.1016/j.tcs.2023.114182 2023

  3. [3]

    A. Amir, Y. Aumann, G. Landau, M. Lewenstein, and N. Lewenstein. Pattern matching with swaps.Journal of Algorithms, 37:247–266, 2000.doi:10.1006/jagm.2000.1120

    work page doi:10.1006/jagm.2000.1120 2000

  4. [4]

    Amir and M

    A. Amir and M. Itzhaki. Reconstructing General Matching Graphs. In35th Annual Symposium on Combinatorial Pattern Matching (CPM), pages 2:1–2:15, 2024.doi: 10.4230/LIPIcs.CPM.2024.2

    work page doi:10.4230/lipics.cpm.2024.2 2024

  5. [5]

    A. Amir, M. Lewenstein, and E. Porat. Faster algorithms for string matching withk mismatches.Journal of Algorithms, 50(2):257–275, 2004.doi:10.1016/S0196-6774(03) 00097-X

    work page doi:10.1016/s0196-6774(03 2004

  6. [6]

    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.doi:10.1007/978-3-319-07566-2_3

    work page doi:10.1007/978-3-319-07566-2_3 2014

  7. [7]

    Apostolico, D

    A. Apostolico, D. Breslauer, and Z. Galil. Optimal parallel algorithms for periods, palin- dromes and squares. InProc. 19th International Colloquium on Automata, Languages, and Programming (ICALP), volume 623, pages 296–307, 1992.doi:10.1007/3-540-55719-9_ 82

    work page doi:10.1007/3-540-55719-9_ 1992

  8. [8]

    Bathie, P

    G. Bathie, P. Charalampopoulos, and T. Starikovskaya. Longest Common Extensions with Wildcards: Trade-Off and Applications. In32nd Annual European Symposium on Algo- rithms (ESA), volume 308, pages 19:1–19:17, 2024.doi:10.4230/LIPIcs.ESA.2024.19

    work page doi:10.4230/lipics.esa.2024.19 2024

  9. [9]

    Bathie, P

    G. Bathie, P. Charalampopoulos, and T. Starikovskaya. Pattern matching with mismatches and wildcards. In32nd Annual European Symposium on Algorithms (ESA), pages 20:1– 20:15, 2024.doi:10.4230/LIPIcs.ESA.2024.20

    work page doi:10.4230/lipics.esa.2024.20 2024

  10. [10]

    Boneh, D

    I. Boneh, D. Fried, S. Golan, and M. Kraus. Hamming distance oracle, 2024.arXiv: 2407.05430,doi:10.48550/arXiv.2407.05430

    work page doi:10.48550/arxiv.2407.05430 2024

  11. [11]

    Borozdin, D

    K. Borozdin, D. Kosolobov, M. Rubinchik, and A.M. Shur. Palindromic length in linear time. In28th Annual Symposium on Combinatorial Pattern Matching (CPM), volume 78, pages 23:1–23:12, 2017.doi:10.4230/LIPIcs.CPM.2017.23. 15

    work page doi:10.4230/lipics.cpm.2017.23 2017

  12. [12]

    T.M. Chan, C. Jin, V.V. Williams, and Y. Xu. Faster algorithms for text-to-pattern hamming distances. InProc. 64th IEEE Symposium on Foundations of Computer Science (FOCS), pages 2188–2203, 2023.doi:10.1109/FOCS57990.2023.00136

    work page doi:10.1109/focs57990.2023.00136 2023

  13. [13]

    Charalampopoulos, S.P

    P. Charalampopoulos, S.P. Pissis, and J. Radoszewski. Longest palindromic substring in sublinear time. In33rd Annual Symposium on Combinatorial Pattern Matching (CPM), volume 223, pages 20:1–20:9, 2022.doi:10.4230/LIPIcs.CPM.2022.20

    work page doi:10.4230/lipics.cpm.2022.20 2022

  14. [14]

    Clifford and R

    P. Clifford and R. Clifford. Simple deterministic wildcard matching.Information Processing Letters, 101(2):53–54, 2007.doi:10.1016/j.ipl.2006.08.002

    work page doi:10.1016/j.ipl.2006.08.002 2007

  15. [15]

    R. Cole, L. Gottlieb, and M. Lewenstein. Dictionary matching and indexing with errors and don’t cares. InProc. 36th Annual ACM Symposium on Theory of Computing (STOC), pages 91–100, 2004.doi:10.1145/1007352.1007374

    work page doi:10.1145/1007352.1007374 2004

  16. [16]

    Cole and R

    R. Cole and R. Hariharan. Verifying candidate matches in sparse and wildcard matching. InProc. 34th Annual ACM Symposium on Theory of Computing (STOC), pages 592–601, 2002.doi:10.1145/509907.509992

    work page doi:10.1145/509907.509992 2002

  17. [17]

    Fischer and M.S

    M.J. Fischer and M.S. Paterson. String matching and other products. In R.M. Karp, editor,Complexity of Computation, volume 7 ofSIAM-AMS Proceedings, pages 113–125. American Mathematical Society, 1974. URL:dspace.mit.edu/handle/1721.1/148870, doi:10.5555/889566

    work page doi:10.5555/889566 1974

  18. [18]

    Consciousness and Cognition20(2011) https://doi.org/10.1016/j

    T. Flouri, E. Giaquinta, K. Kobert, and E. Ukkonen. Longest common substrings with kmismatches.Information Processing Letters, 115(6–8):643–647, 2015.doi:10.1016/j. ipl.2015.03.006

    work page doi:10.1016/j 2015

  19. [19]

    Fuglsang

    A. Fuglsang. Distribution of potential type II restriction sites (palindromes) in prokaryotes. Biochemical and Biophysical Research Communications, 310(2):280–285, 2003.doi:10. 1016/j.bbrc.2003.09.014

    2003

  20. [20]

    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, 1975.doi: 10.1145/990502.990505

    work page doi:10.1145/990502.990505 1975

  21. [21]

    Galil and R

    Z. Galil and R. Giancarlo. Improved string matching withkmismatches.SIGACT News, 17(4):52–54, 1986.doi:10.1145/8307.8309

    work page doi:10.1145/8307.8309 1986

  22. [22]

    Galil and J

    Z. Galil and J. Seiferas. Recognizing certain repetitions and reversals within strings. In Proc. 17th Annual IEEE Symposium on Foundations of Computer Science (FOCS), pages 236–252, 1976.doi:10.1109/SFCS.1976.25

    work page doi:10.1109/sfcs.1976.25 1976

  23. [23]

    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 Research, 25:2430– 2439, 1997.doi:10.1093/nar/25.12.2430

    work page doi:10.1093/nar/25.12.2430 1997

  24. [24]

    P. Indyk. Deterministic superimposed coding with applications to pattern matching. In Proc. 38th IEEE Symposium on Foundations of Computer Science (FOCS), pages 127–136, 1997.doi:10.1109/SFCS.1997.646101

    work page doi:10.1109/sfcs.1997.646101 1997

  25. [25]

    M. Itzhaki. Combinatorics of palindromes. InFundamentals of Computation Theory (FCT), pages 252–266, 2025.doi:10.1007/978-3-032-04700-7_19

    work page doi:10.1007/978-3-032-04700-7_19 2025

  26. [26]

    M. Itzhaki. Asymptotically optimal representation of palindromic structure. InSOFSEM 2026: Theory and Practice of Computer Science, pages 128–143. Springer Nature Switzer- land, 2026.doi:10.1007/978-3-032-17801-5_10. 16

    work page doi:10.1007/978-3-032-17801-5_10 2026

  27. [27]

    A. Kalai. Efficient pattern-matching with don’t cares. InProc. 13th Annual ACM-SIAM Symposium on Discrete Algorithms (SODA), pages 655–656, 2002.doi:10.5555/545381. 545468

    work page doi:10.5555/545381 2002

  28. [28]

    Kaplan, E

    H. Kaplan, E. Porat, and N. Shafrir. Finding the position of thek-mismatch and approxi- mate tandem repeats. InProc. 12th Scandinavian Workshop on Algorithm Theory (SWAT), pages 90–101, 2006.doi:10.1007/11785293_11

    work page doi:10.1007/11785293_11 2006

  29. [29]

    Kasai, G

    T. Kasai, G. Lee, H. Arimura, S. Arikawa, and K. Park. Linear-time longest-common-prefix computation in suffix arrays and its applications. InProc. 12th Symposium on Combinato- rial Pattern Matching (CPM), pages 181–192, 2001.doi:10.1007/3-540-48194-X_17

    work page doi:10.1007/3-540-48194-x_17 2001

  30. [30]

    Knuth, J.H

    D.E. Knuth, J.H. Morris, and V.R. Pratt. Fast pattern matching in strings.SIAM Journal on Computing, 6:323–350, 1977.doi:10.1137/0206024

    work page doi:10.1137/0206024 1977

  31. [31]

    Kolpakov and G

    R. Kolpakov and G. Kucherov. Searching for gapped palindromes.Theoretical Computer Science, 410(51):5365–5373, 2009.doi:10.1016/j.tcs.2009.09.013

    work page doi:10.1016/j.tcs.2009.09.013 2009

  32. [32]

    Landau and U

    G.M. Landau and U. Vishkin. Efficient string matching in the presence of errors. InProc. 26th IEEE Symposium on Foundations of Computer Science (FOCS), pages 126–136, 1985. doi:10.1109/SFCS.1985.22

    work page doi:10.1109/sfcs.1985.22 1985

  33. [33]

    A. Lenz, A. Wachter-Zeh, and E. Yaakobi. Duplication-correcting codes.Designs, Codes and Cryptography, 87(2):277–298, 2019.doi:10.1007/s10623-018-0523-0

    work page doi:10.1007/s10623-018-0523-0 2019

  34. [34]

    Lisnic, I.K

    B. Lisnic, I.K. Svetec, H. Saric, I. Nikolic, and Z. Zgaga. Palindrome content of the yeast Saccharomyces cerevisiae genome.Current Genetics, 47:289–297, 2005.doi:10.1007/ s00294-005-0573-5

    2005

  35. [35]

    W. Maass. Quadratic lower bounds for deterministic and nondeterministic one-tape tur- ing machines (extended abstract). InProc. 16th Annual ACM Symposium on Theory of Computing (STOC), pages 401–408, 1984.doi:10.1145/800057.808706

    work page doi:10.1145/800057.808706 1984

  36. [36]

    Manacher

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

    work page doi:10.1145/321892.321896 1975

  37. [37]

    Rubinchik and A.M

    M. Rubinchik and A.M. Shur. EERTREE: An efficient data structure for processing palindromes in strings.European Journal of Combinatorics, 68:249–265, 2018.doi: 10.1016/j.ejc.2017.07.021

    work page doi:10.1016/j.ejc.2017.07.021 2018

  38. [38]

    Slisenko

    A.O. Slisenko. Recognition of palindromes by multihead turing machines. InProceedings of the Steklov Institute of Mathematics, volume 129, pages 30–202. American Mathematical Society, 1973

    1973

  39. [39]

    D. Sokol. 2-dimensional palindromes with k mismatches.Information Processing Letters, 164:106019, 2020.doi:10.1016/j.ipl.2020.106019

    work page doi:10.1016/j.ipl.2020.106019 2020

  40. [40]

    Srivastava and H.S

    S.K. Srivastava and H.S. Robins. Palindromic nucleotide analysis in human T cell receptor rearrangements.PLoS One, 7(12):e52250, 2012.doi:10.1371/journal.pone.0052250. 17

    work page doi:10.1371/journal.pone.0052250 2012