Plus longue sous-séquence palindrome à la main

Séquences et chaînes de caractères · niveau 1 (application)

Énoncé

Soit $S = character$ ( $n = 9$ ) et $l (i, j)$ la longueur d'une plus longue sous-séquence palindrome de $S [i : j]$ .

Rappeler la récurrence et l'ordre de calcul.
Calculer les valeurs $l (i, j)$ utiles pour obtenir $l (0, 9)$ , et en déduire une plus longue sous-séquence palindrome.

Corrigé

$l (i, i) = 0$ , $l (i, i + 1) = 1$ ; pour $j - i \geq 2$ , si $s_{i} = s_{j - 1}$ alors $l (i, j) = 2 + l (i + 1, j - 1)$ , sinon $l (i, j) = max {l (i + 1, j), l (i, j - 1)}$ . On calcule par tailles $t = j - i$ croissantes.
Le tableau calculé par le programme (ligne $i$ , colonnes $j$ de $0$ à $9$ ) :


i=0 : 0 1 1 1 1 3 5 5 5 5
i=1 : . 0 1 1 1 3 3 3 3 3
i=2 : . . 0 1 1 3 3 3 3 3
i=3 : . . . 0 1 1 1 1 1 3
i=4 : . . . . 0 1 1 1 1 1

Lecture : $s_{0} = c \neq = s_{8} = r$ et $l (0, 9) = l (0, 8) = \dots = l (0, 6) = 5$ ; $s_{0} = s_{5} = c$ , donc $l (0, 6) = 2 + l (1, 5)$ avec $l (1, 5) = 3$ (ara dans hara). Une plus longue sous-séquence palindrome est carac, de longueur $5$ .


nom : S
valeurs : c h a r a c t e r
vert : 0 2 3 4 5
fleches : 0->5 2->4
legende : carac : s0 = s5 = c, puis ara dans hara