4 papers
cs.DS2026
On Time-Memory Tradeoffs for Maximal Palindromes with Wildcards and -Mismatches
Amihood Amir, Ayelet Butman, Michael Itzhaki +1
This paper addresses the problem of identifying palindromic factors in texts that include wildcards -- special characters that match all others. These symbols challenge many classi…
cs.DS2025
Combinatorics of Palindromes
Michael Itzhaki
We investigate the structure and reconstruction complexity of Manacher arrays. First, we establish a combinatorial lower bound, proving that the number of rooted tandem repeat tree…
cs.DS2024
Asymptotically Optimal Representation of Palindromic Structure
Michael Itzhaki
We introduce an asymptotically optimal representation of the Manacher array of a string that supports constant-time access. The approach relies on the combinatorial properties of p…
cs.DS2024
Explicit Combinatoric Structures of Palindromes and Chromatic Number of Restriction Graphs
Amihood Amir, Michael Itzhaki
The palindromic fingerprint of a string is the set . In this work, w…