Longueur palindromique d'un mot
# Longueur palindromique d'un mot

En combinatoire, et plus particulièrement en combinatoire des mots, la longueur palindromique d'une chaîne est le nombre minimum de palindromes dont la concaténation est égale à cette chaîne. Les mots de longueur palindromique égale à 1 sont les palindromes.

## Exemples

Notons $p(w)$ la longueur palindromique d'un mot $w$. Le mot abaab est le produit des deux palindromes a et baab sans être lui-même un palindrome ; sa longueur palindromique est 2. Le mot abaca est de longueur palindromique $p$(abaca)=3.

Chaque lettre est un palindrome, et un mot de longueur n est produit de n palindromes de longueur 1 ; la longueur palindromique d'un mot de longueur $n$ est au plus $n$.

Le mot 010011 peut être exprimé de deux façons différentes comme produite de trois palindromes :(0)(1001)(1) et (010)(0)(11).

## Une majoration

Notons $p(w)$ la longueur palindromique d'un mot $w$. Alexander (ou Olexandr) Ravsky a donné, en 2003, une formule précises pour le maximum des longueurs palindromiques des mots binaires de longueur donnée. Notons de maximum $K(n)$ :

    $K(n)=\max\{p(w)\mid |w|=n\}$.

Alors on a :

    $K(n)=[n/6]+[(n+4)/6]+1$ pour $n\neq 11$ et $K(11)=5$.

Par exemple, $K(30)=11$ ; ainsi tout mot binaire de longueur 30 est produit d'au plus 11 palindromes, et cette valeur est atteinte.

## Algorithmes

Le calcul de la longueur palindromique est un problème de combinatoire algorithmique des mots. Plusieurs algorithmes ont été présentés qui calculent la longueur palindromique d'un mot de longueur $n$ en temps $O(n\log \,n)$$^,.$ En 2017, Borozdin, Kosolobov , Rubinchik et Shur présentent, au Symposium on Combinatorial Pattern Matching, un algorithme linéaire ; de plus c'est un algorithme en ligne, c'est-à-dire qu'il lit la chaîne séquentiellement et de gauche à droite et calcule la longueur palindromique de chaque préfixe après en avoir lu le dernier caractère. Toutefois, les auteurs disent eux-mêmes que la constante du terme linéaire est telle qu'en pratique un algorithme en $O(n\log \,n)$ est plus rapide.

Un algorithme simple, en temps quadratique et en place linéaire pour calculer la longueur palindromique $p(w)$ d'un mot $w$ de longueur n est basé sur la formule suivante :

    $p(w[1..j])=\min _{i}\{1+p(w[1..i-1])\mid i\leq j,w[i..j]\ {\text{est un palindrome}}\}$

On remplit un tableau de taille $n$, noté $P$, où $P[i]$ est la longueur palindromique du préfixe $w[1..i]$ de longueur $i$ de $w$. À chaque étape $j$, on calcule l'ensemble $P_{j}$ des positions de départ des suffixes de $w[1..j]$ qui sont des palindromes ; on les obtient à partir des positions de départ de $P_{j-1}$ des suffixes de $w[1..j-1]$ en utilisant le fait que $w[i..j]$ est un palindrome si et seulement si $w[i+1..j-1]$ est un palindrome et $w[i]=w[j]$. La place requise est clairement linéaire ; on utilise un temps en $O(|P_{j}|+|P_{j-1}|)$ à chaque étape, de sorte que le temps requis est proportionnel au nombre de facteurs palindromiques du mot. Ce nombre peut être quadratique, comme pour le mot $(ab)^{n/2}$. L'algorithme peut être facilement adapté pour donner une factorisation en palindromes.

## Mots infinis

Le mot de Thue-Morse est un mot infini dont tous les préfixes d'une longueur une puissance de 4 est un palindrome ; ce sont

Les préfixes dont la longueur est 2 fois une puissance de 4 sont produits de deux palindromes. Frid, Puzynina et Zamboni ont montré que dans le mot de Thue-Morse, et plus généralement dans un mot qui ne contient pas en facteur des puissances arbitrairement élevées, il y a des préfixes de longueur palindromiques arbitrairement grande. Plus précisément, ils prouvent que pour un entier $k$ et un mot infini $w$ sans puissance $k$-ième, et pour tout entier $m$, il existe un préfixe $u$ de $w$ de longueur palindromique $p(u)>m$.

Les auteurs se demandent s'il existe un mot infini non ultimement périodique pour lequel les longueurs palindromiques de tous ses préfixes est bornée. Anna Frid a prouvé que ceci est impossible dans le cas des mots sturmiens.

La suite des longueurs palindromiques $p_{n}(u)$ des préfixes de longueur n d'un mot infini u est 2-régulière dans le cas du mot de Thue-Morse qui est 2-automatique. Plus généralement, la suite $p_{n}(u)$ d'un mot $k$-automatique ne qu'un nombre fini de palindromes est $k$-régulière. Pour deux mots automatiques, à savoir le mot du pliage de papier et le mot de Rudin-Shapiro, la suite admet une forme explicite.

La suite des différences

    $d_{n}(u)=p_{n+1}(u)-p_{n}(u)$

des longueurs palindromiques des préfixes de $u$, avec la convention $d_{0}(u)=1$ ne prend que trois valeurs, à savoir -1,0, ou 1. Ceci résulte de l'encadrement

    $p_{n}(u)-1\leq p_{n+1}\leq p_{n}(u)+1$

démontré dans cette forme par Saarela. Elle a la propriété suivante : Si un mot infini $k$-automatique $u$ ne contient qu'un nombre fin de palindromes distincts, alors la suite des différences est également $k$-automatique. L'hypothèse est remplie par les mots du pliage de papier et de Rudin-Shapiro. Les automates pour ces suites sont assez volumineux.

