Plus longue sous-séquence commune à la main — exercice corrigé d'algorithmique (école d'ingénieur) (chapitre 8)

Plus longue sous-séquence commune à la main

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

Énoncé

Soit $T = CHIMPANZE$ et $U = HUMAIN$ .

Calculer le tableau $L$ de terme général $l (p, q)$ , longueur d'une plsc aux $p$ - et $q$ -préfixes de $T$ et $U$ .
En déduire $l (9, 6)$ et une plsc, en suivant la reconstruction du cours.
On modifie la fonction plsc pour qu'elle préfère la case de gauche $(p, q - 1)$ à la case du dessus $(p - 1, q)$ en cas d'égalité. Obtient-on la même plsc ? Y en a-t-il plusieurs ?

Corrigé

On remplit $L$ ligne par ligne : si les symboles sont égaux, $l (p, q) = 1 + l (p - 1, q - 1)$ , sinon $l (p, q) = max {l (p - 1, q), l (p, q - 1)}$ .


    H U M A I N
  0 0 0 0 0 0 0
C 0 0 0 0 0 0 0
H 0 1 1 1 1 1 1
I 0 1 1 1 1 2 2
M 0 1 1 2 2 2 2
P 0 1 1 2 2 2 2
A 0 1 1 2 3 3 3
N 0 1 1 2 3 3 4
Z 0 1 1 2 3 3 4
E 0 1 1 2 3 3 4

$l (9, 6) = 4$ . En partant de la case $(9, 6)$ : E et Z sont inutiles (on monte), N $=$ N (diagonale), puis A, M, H : la plsc est HMAN.


nom : T
valeurs : C H I M P A N Z E
vert : 1 3 5 6


nom : U
valeurs : H U M A I N
vert : 0 2 3 5
legende : la plsc HMAN

On obtient encore HMAN : c'est ici la seule plsc (on peut le vérifier en énumérant les sous-séquences de longueur $4$ de HUMAIN). En général, changer la préférence peut changer la plsc retournée, jamais sa longueur.


static String plscGauche(String T, String U, int[][] L, int p, int q) {
    if (p == 0 || q == 0) return "";
    if (T.charAt(p - 1) == U.charAt(q - 1))
        return plscGauche(T, U, L, p - 1, q - 1) + T.charAt(p - 1);
    if (L[p][q] == L[p][q - 1]) return plscGauche(T, U, L, p, q - 1); // u(q-1) inutile
    return plscGauche(T, U, L, p - 1, q);
}