Plus courte sur-séquence commune — exercice corrigé d'algorithmique (école d'ingénieur) (chapitre 8)

Plus courte sur-séquence commune

Séquences et chaînes de caractères · niveau 3 (difficile)

Énoncé

Une sur-séquence commune à $T$ et $U$ est une séquence dont $T$ et $U$ sont deux sous-séquences.

Montrer que la longueur d'une plus courte sur-séquence commune est $m + n - l (m, n)$ , où $l (m, n)$ est la longueur d'une plsc.
Écrire une fonction récursive, guidée par le tableau $L$ , qui retourne une plus courte sur-séquence commune.
L'appliquer à $T = ABCBDAB$ et $U = BDCABA$ .

Corrigé

Dans une sur-séquence commune $W$ , les symboles qui servent à la fois à $T$ et à $U$ forment une sous-séquence commune ; les autres servent à un seul des deux. Donc $∣ W ∣ \geq m + n - l (m, n)$ . Réciproquement, en fusionnant $T$ et $U$ le long d'une plsc (chaque symbole de la plsc écrit une seule fois), on obtient une sur-séquence de longueur $m + n - l (m, n)$ .
La fusion suit la reconstruction de la plsc ; quand un symbole est « inutile » à la plsc, on l'écrit quand même :


static String pcsc(String T, String U, int[][] L, int p, int q) {
    if (p == 0) return U.substring(0, q);            // il ne reste que U[0:q]
    if (q == 0) return T.substring(0, p);
    if (T.charAt(p - 1) == U.charAt(q - 1))          // symbole de la plsc, écrit une fois
        return pcsc(T, U, L, p - 1, q - 1) + T.charAt(p - 1);
    if (L[p][q] == L[p - 1][q]) return pcsc(T, U, L, p - 1, q) + T.charAt(p - 1);
    return pcsc(T, U, L, p, q - 1) + U.charAt(q - 1);
}

Ici $m = 7$ , $n = 6$ et $l (7, 6) = 4$ : la longueur minimum est $7 + 6 - 4 = 9$ .


pcsc(ABCBDAB, BDCABA) = ABDCABDAB (longueur 9)


valeurs : A B D C A B D A B
vert : 1 3 5 7
legende : en vert, la plsc BCBA, écrite une seule fois : 7 + 6 - 4 = 9