title: Arbre palindromique
text: # Arbre palindromique
  
  Un arbre palindrome ou arbre palindromique, aussi appelé arbre eertree, est un graphe utilisé pour des algorithmes de combinatoire des mots.
  
  ## Description
  
  L'arbre palindrome pour un mot $S$ de longueur $n$ est une structure de donnée sous forme d'un graphe proche d'un arbre et qui représentent tous les palindromes distincts qui sont facteurs de $S$ avec une place additionnelle en $O(n)$. Lorsque $S$ est de longueur $n$ sur un alphabet de taille $\sigma$ et est donnée on-line, l'arbre peut être construit en temps $O(n\log \sigma )$ et place $O(n)$.
  
  Les sommets du graphe représentent des palindromes, les arcs décrivent le passage d'un palindrome au suivant ou à un précédent.
  
  Il y a deux types d'arcs, des arcs directs — qui sont les arcs d'un arbre — et des liens suffixes qui permettent de revenir en arrière.
  
  Les arcs directs sont étiquetés par des symboles de l'alphabet. Il y a un arc direct du sommet $u$ vers le sommet $v$ étiqueté par la lettre $a$ si $v=aua$ :
  
      $u\xrightarrow {a} v\iff v=aua$.
  
  Ainsi, on a dans l'exemple, les arcs
  
      ${\mathsf {t}}\xrightarrow {\mathsf {r}} {\mathsf {rtr}}\xrightarrow {\mathsf {e}} {\mathsf {ertre}}\xrightarrow {\mathsf {e}} {\mathsf {eertree}}$.
  
  Les liens suffixes sont des arcs qui vont d'un sommet $u$ au sommet $v$, où $v$ est le plus long suffixe palindrome propre de $u$. Dans l'exemple, les liens suffixes sont tracés en rouge. On a par exemple :
  
      ${\mathsf {eertree}}\ {\color {Red}\to }\ {\mathsf {ee}}\ {\color {Red}\to }\ {\mathsf {e}}\ {\color {Red}\to }\ 0$.
  
  Deux sommets spéciaux sont ajoutés à la structure :
  
  * le sommet $-1$ qui est la racine de l'arbre ; les arcs sortant de ce sommet et étiqueté $a$ ont pour extrémité le sommet $a$ ; on a donc, pour tout symbole figurant dans $S$, l'arc
  
         $-1\xrightarrow {a} a$.
  * Le sommet $0$ qui représente le mot vide (qui est un palindrome) ; on a alors
  
         $0\xrightarrow {a} aa$
      si $aa$ est facteur de $S$. Le sommet $0$ est le lien suffixe du sommet $-1$ et de lui-même.
  
  La notation curieuse pour ces sommets particuliers est une conséquence de la numérotation des sommets de l'arbre, qui va de 1 jusqu'à un entier qui est aussi le nombre de palindromes figurant dans le mot $S$.
  
  ## Complexité
  
  On peut montrer que la construction de l'arbre palindromique peur se faire en temps $O(n\log \sigma )$ et place $O(n)$. Des variantes ont été données notamment par Mieno, Watanabe et al..
  
  