CLR cover
Previous problem

Problem 91: Palindromic Concatenation of Palindromes

Next problem

Palindromes constitute another type of regularity different from periodicity. They appear naturally in data folding when the process requires segments of data to be matched like in some genomic sequences. The problem deals with palindromes occurring in a product of palindromes.

Given a finite set of words $X$, computing the number of all palindromes in $X^2$ can be easily done in $n\cdot |X|$ time, where $n$ is the total length of words in $X$. However, there is a much simpler and more efficient method when $X$ is itself a set of palindromes.

Given a finite set $X$ of binary palindromes whose total length is $n$, design an algorithm computing the number of (distinct) palindromes in $X^2$ and running in time $O(n+|X|^2)$.
When $x$ and $y$ are palindromes, $xy$ is also a palindrome if and only if $xy=yx$.