Plus longue sous-séquence commune (LCS)

Énoncé

Le programme lit deux chaînes de caractères (une par ligne) et affiche deux lignes : la longueur de la plus longue sous-séquence commune, puis une instance de cette sous-séquence. Une sous-séquence est obtenue en supprimant zéro ou plusieurs caractères sans modifier l'ordre des caractères restants (les caractères ne doivent pas être contigus). Si plusieurs LCS de même longueur existent, afficher celle obtenue par remontée de la matrice de DP de haut-gauche vers bas-droite (choix lexicographique déterministe).

Contraintes

• Chaque chaîne contient entre 0 et 1 000 caractères ASCII imprimables.
• Si l'une des chaînes est vide, la LCS est vide et sa longueur est 0 — afficher 0 puis une ligne vide.
• La comparaison est sensible à la casse.
• Complexité attendue : O(N × M) en temps et en espace.
• Solution réalisable dans tout langage généraliste avec sa seule bibliothèque standard.

Exemple

CopierEntrée :
ABCBDAB
BDCAB

Sortie :
4
BCAB

CopierEntrée :
AGGTAB
GXTXAYB

Sortie :
4
GTAB