## Example

\(
\def\sa#1{\tt{#1}}
\def\dd{\dot{}\dot{}}
\newcommand{\Forest}{\mathcal{P}}%
\newcommand{\ps}{\mathit{palsuf}}%
\newcommand{\upward}{\mathit{upward}}%
\newcommand{\Arrow}[1]{\,\stackrel{#1}{\longrightarrow}\,}
\)

The picture shows the forest
$\Forest(\sa{ababbababaab})$ that comprises three palindrome trees.

#
Problem 92: Palindrome Trees

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.