CLR cover
Previous problem

Problem 92: Palindrome Trees

Next problem

The notion of a palindrome forest $\Forest(x)$ provides a structural representation of all palindromes occurring in a word $x$. The data structure is used to perform different operations on the set of palindromic factors, such as to access efficiently to the longest palindrome ending at a given position on $x$ or to count the number of occurrences of each palindrome in $x$.

The forest consists of a collection of trees in which each represents all palindromic factors in a similar way as a Suffix tree represents all factors. Suffix links are also part of the structure to get an efficient construction. However, palindrome forests are simpler than Suffix trees, since each edge is labelled by a single letter.

Each node of $\Forest(x)$ is a palindrome occurring in $x$. From a node $z$, there is an edge $z\Arrow{a} aza$ labelled by the letter $a$ if $aza$ is a palindrome in $x$. The empty word $\varepsilon$ is the root of the tree for even palindromes. And each letter occurring in $w$ is the root of a tree for odd palindromes having the letter at their centre.

Each node of the trees can be represented by an interval $[i\dd j]$ of positions corresponding to an occurrence of the palindrome $x[i\dd j]$. The palindrome is also fully determined by the path from the root to the node.

Assume the alphabet is of constant size. Show how to construct the palindrome forest of a word in linear time according to the word length.
Use suffix links.

References

  • M. Rubinchik and A. M. Shur. Eertree: An efficient data structure for processing palindromes in strings. CoRR, abs/1506.04862, 2015.