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…