Asymptotically Optimal Representation of Palindromic Structure
Michael Itzhaki · arXiv (Cornell University) · 2024
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 palindromes, yielding a compact yet efficient structure. This work fits within the broader study of compressed text indexing and highlights structural aspects of palindromic substrings that may inspire further algorithmic applications.