La plus longue sous-suite commune

Exercice · informatique (tronc commun des prépas scientifiques), chapitre 18 — La programmation dynamique

Énoncé

La plus longue sous-suite commune (PLSC) de deux chaînes $u$ et $v$ est la suite de caractères de longueur maximale apparaissant dans le même ordre (pas nécessairement contigus) dans les deux chaînes. (a) Définir la récurrence sur la longueur $L (i, j)$ de la PLSC entre les préfixes de taille $i$ de $u$ et $j$ de $v$ . (b) Implémenter l'algorithme, calculer la PLSC pour les mots "BATEAU" et "TABLEAU", et reconstruire la solution. (c) Citer une application quotidienne de cet algorithme.

Corrigé

(a) Si les derniers caractères des préfixes sont identiques ( $u_{i} = v_{j}$ ), ils prolongent la PLSC. Sinon, le caractère optimal provient soit de l'exclusion de $u_{i}$ , soit de l'exclusion de $v_{j}$ : $L (i, j) = ⎩ ⎨ ⎧ 0 L (i - 1, j - 1) + 1 max (L (i - 1, j), L (i, j - 1)) si i = 0 ou j = 0 si u_{i} = v_{j} sinon$ (b)

def plsc(u: str, v: str) -> str:
    n, m = len(u), len(v)
    L = [[0] * (m + 1) for _ in range(n + 1)]
    for i in range(1, n + 1):
        for j in range(1, m + 1):
            if u[i - 1] == v[j - 1]:
                L[i][j] = L[i - 1][j - 1] + 1
            else:
                L[i][j] = max(L[i - 1][j], L[i][j - 1])
    
    # Reconstruction à rebours
    i, j, lettres = n, m, []
    while i > 0 and j > 0:
        if u[i - 1] == v[j - 1]:
            lettres.append(u[i - 1])
            i -= 1
            j -= 1
        elif L[i - 1][j] >= L[i][j - 1]:
            i -= 1
        else:
            j -= 1
    return "".join(reversed(lettres))

plsc("BATEAU", "TABLEAU") renvoie "BEAU" (ou "TEAU", de longueur 4). (c) C'est l'algorithme utilisé par la commande diff (et par Git) pour identifier les lignes ajoutées ou supprimées entre deux versions d'un fichier source.

Les autres exercices de ce chapitre Le cours du chapitre

Un blocage sur cet exercice ? Le tuteur d'Adloun guide par questions, sans donner la réponse.