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). Plusieurs sous-séquences communes de longueur maximale peuvent exister : n'importe laquelle convient, seule sa longueur est imposée. Les exemples ci-dessous en montrent une parmi les réponses valides.

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