Tableau de Lyndon

Le tableau de Lyndon ${\displaystyle L}$ d'une chaîne ${\displaystyle w}$ est un tableau de même taille tel que ${\displaystyle L[i]}$ est la longueur du plus long facteur de ${\displaystyle w}$ commençant en position ${\displaystyle i}$ qui est un mot de Lyndon. Formellement :

${\displaystyle L[i]=\max\{h:w[i,i+h-1]{\text{ est un mot de Lyndon}}\}.}$

Exemple

Les tableaux sont numérotés à partir de 0. Soit ${\displaystyle w=00011001}$. Le tableau de Lyndon du mot est donné dans la dernière colonne ci-dessous :

Indice	Lyndon	L
0	00011001	8
1	0011	4
2	011	3
3	1	1
4	1	1
5	001	3
6	01	2
7	1	1

Le tableau de Lyndon est

${\displaystyle L=(8,4,3,1,1,3,2,1)}$.

Deux autres tableaux sont liés au tableau de Lyndon d'un mot, d'une part le tableau des suffixes et d'autre part le tableau dites des valeurs inférieures suivantes :

Le tableau des valeurs inférieures suivantes (en anglais next smaller value array) ${\displaystyle N=N_{A}}$ est défini pour un tableau d'entiers ${\displaystyle A[1,n]}$ ; il contient, pour l'indice ${\displaystyle i}$, le plus petit indice d'une valeur dans ${\displaystyle A[i+1,n]}$ qui est plus petite que ${\displaystyle A[i]}$ ; si une telle valeur n'existe pas, le tableau contient pour cet indice la valeur maximale ${\displaystyle n}$. Formellement,

${\displaystyle N_{A}[i]=\min {\{n\}\cup \{j\mid j>i{\text{ et }}A[j]<A[i]\}}.}$.

Par exemple, pour le tableau

${\displaystyle A=(8,4,3,1,1,3,2,1)}$,

le tableau des valeurs inférieures suivantes est

${\displaystyle N=N_{A}=(1,2,3,8,8,6,7,8)}$.

Franek et al.[1] ont montré que le tableau de Lyndon se calcule facilement en temps linéaire en appliquant la construction du next smaller value array à l'inverse du tableau des suffixes : si on note ${\displaystyle S}$ le tableau des suffixe du mot et ${\displaystyle U}$ l'inverse de ce tableau (de sorte que ${\displaystyle S[i]=j}$ ssi ${\displaystyle U[j]=i}$), alors le tableau de Lyndon est donné par la formule

${\displaystyle L[i]=N_{U}[i]-i}$.

Exemple

Pour le mot ${\displaystyle w=00011001}$, le tableau des suffixes - qui donne la longueurs des suffixes dans l'ordre lexicographique - est

${\displaystyle S=S(w)=(0,5,1,6,2,7,4,3)}$

et le tableau des inverses est

${\displaystyle U=(0,2,4,7,6,1,3,5)}$.

Le tableau des valeurs inférieures suivantes pour U est

${\displaystyle N=N_{U}=(8,5,5,4,5,8,8,8)}$.

La formule ${\displaystyle L[i]=N_{U}[i]-i}$ donne

${\displaystyle N_{U}-I=(8,4,3,1,1,3,3,1)=L}$ !