La plus longue sous-suite commune

La programmation dynamique · niveau 2

É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.

Énoncé

Corrigé

Exercices semblables