Introduction au problème LCS

La recherche de la Plus Longue Sous-Séquence Commune (LCS - Longest Common Subsequence) est un défi algorithmique classique. Contrairement à une sous-chaîne, les éléments d'une sous-séquence n'ont pas besoin d'être contigus dans les chaînes d'origine, mais ils doivent conserver leur ordre relatif. Ce concept est au cœur de nombreux outils comme la commande diff sous Unix, les systèmes de contrôle de version (Git) et l'analyse de séquences d'ADN en bio-informatique.

Principes fondamentaux et approche récursive

Le problème LCS repose sur deux propriétés majeures de la programmation dynamique :

• Structure optimale : La solution globale peut être construite à partir des solutions de sous-problèmes. Si deux caractères finaux correspondent, ils font partie de la LCS. Sinon, la solution est le maximum des deux sous-problèmes possibles en excluant un caractère de l'une ou l'autre chaîne.
• Chevauchement des sous-problèmes : Un calcul réactif naïf résoudra plusieurs fois les mêmes segments de chaînes, d'où l'importance de stocker les résultats intermédiaires.

Méthode 1 : Programmation Dynamique Tabulaire (Bottom-Up)

Cette approche utilise une matrice bidimensionnelle pour stocker les longueurs des sous-séquences communes calculées de manière itérative. C'est l'implémentation la plus stable pour éviter les débordements de pile.

#include <stdio.h>
#include <string.h>
#include <stdlib.h>

#define MAX(a, b) ((a) > (b) ? (a) : (b))

void resoudre_lcs_standard(char *txt1, char *txt2) {
    int len1 = strlen(txt1);
    int len2 = strlen(txt2);
    int grille[len1 + 1][len2 + 1];

    // Remplissage de la matrice de scores
    for (int i = 0; i <= len1; i++) {
        for (int j = 0; j <= len2; j++) {
            if (i == 0 || j == 0)
                grille[i][j] = 0;
            else if (txt1[i - 1] == txt2[j - 1])
                grille[i][j] = grille[i - 1][j - 1] + 1;
            else
                grille[i][j] = MAX(grille[i - 1][j], grille[i][j - 1]);
        }
    }

    // Reconstruction de la séquence à rebours
    int taille_lcs = grille[len1][len2];
    char *resultat = (char *)malloc((taille_lcs + 1) * sizeof(char));
    resultat[taille_lcs] = '\0';

    int r = len1, c = len2;
    while (r > 0 && c > 0) {
        if (txt1[r - 1] == txt2[c - 1]) {
            resultat[taille_lcs - 1] = txt1[r - 1];
            r--; c--; taille_lcs--;
        } else if (grille[r - 1][c] > grille[r][c - 1]) {
            r--;
        } else {
            c--;
        }
    }

    printf("Séquence LCS : %s (Longueur : %d)\n", resultat, grille[len1][len2]);
    free(resultat);
}

Méthode 2 : Mémoïsation (Top-Down)

Cette technique utilise la récursivité tout en conservant une table de cache pour éviter les calculs redondants. Elle est souvent plus intuitive à écrire à partir de la définition mathématique.

int cache[100][100]; // Initialisé à -1

int lcs_memo(char *s1, char *s2, int m, int n) {
    if (m == 0 || n == 0) return 0;
    
    if (cache[m][n] != -1) return cache[m][n];

    if (s1[m - 1] == s2[n - 1]) {
        return cache[m][n] = 1 + lcs_memo(s1, s2, m - 1, n - 1);
    } else {
        return cache[m][n] = MAX(lcs_memo(s1, s2, m - 1, n), lcs_memo(s1, s2, m, n - 1));
    }
}

Méthode 3 : Optimisation de l'Espace Mémoire

Si seule la longueur de la LCS est requise (et non la séquence elle-même), nous pouvons réduire l'espace de O(m*n) à O(n) en utilisant seulement deux lignes de la matrice (la ligne actuelle et la ligne précédente).

int lcs_espace_reduit(char *s1, char *s2) {
    int m = strlen(s1), n = strlen(s2);
    int dp[2][n + 1];
    int ligne = 0;

    for (int i = 0; i <= m; i++) {
        ligne = i % 2;
        for (int j = 0; j <= n; j++) {
            if (i == 0 || j == 0)
                dp[ligne][j] = 0;
            else if (s1[i - 1] == s2[j - 1])
                dp[ligne][j] = dp[1 - ligne][j - 1] + 1;
            else
                dp[ligne][j] = MAX(dp[1 - ligne][j], dp[ligne][j - 1]);
        }
    }
    return dp[ligne][n];
}

Analyse comparative des performances

Le tableau suivant résume l'efficacité des différentes approches en fonction de la taille des entrées :

Points de vigilance techniques

1. Indices de matrice : La matrice dp[m+1][n+1] est décalée d'une unité par rapport aux index des chaînes (0-based) pour gérer proprement le cas de la chaîne vide.
2. Gestion de la mémoire : Lors de l'utilisation de matrices dynamiques pour des chaînes très longues (plusieurs milliers de caractères), privilégiez malloc sur le tas plutôt que l'allocation sur la pile pour éviter le stack overflow.
3. Séquences multiples : Si les deux branches dp[i-1][j] et dp[i][j-1] sont égales lors de la reconstruction, cela signifie qu'il existe plusieurs LCS de même longueur. L'algorithme standard n'en retourne qu'une.