Considérons les deux « textes » "LAPIN" et "CAPRIN".
À quel point sont-ils proches ?
Pour répondre à cette question, on peut se demander quelle est la plus longue sous-suite commune à ces deux textes.
Définition
On appelle sous-suite d'une chaîne de caractères, une chaîne produite en enlevant zéro, un ou plusieurs caractères.
Par exemple, "AN" est une sous-suite de "LAPIN".
"AN' est aussi une sous-suite commune à "LAPIN" et "CAPRIN".
Dans certains cas, il peut y avoir plusieurs sous-suites communes de longueurs identiques. Par exemple les chaînes "abc" et "bac" admettent deux sous-suites communes de longueur 2 : "ac" et "bc".
On va donc plutôt calculer la longueur de la plus longue sous-suite commune aux deux textes.
La comparaison de "LAPIN" et "CAPRIN" donne ceci (sur fond vert les caractères "identiques", sur fond rouge les "différents") :
LAPIN
CAPRIN
La plus longue sous-suite commune est donc "APIN". Elle est de longueur 4.
Écrire la fonction lplssc (pour longueur plus longue sous-suite commune) qui prend en argument les deux textes à comparer (texte_a et texte_b) et renvoie la longueur de la plus longue sous-suite commune.
On propose deux versions de cette fonction : une version récursive utilisant la mémoïsation et une itérative.
Une approche consiste à déterminer les longueurs des plus longues sous-suites communes de toutes les versions de chaque texte :
la version à 0 caractère, la version à 1 caractère, etc. Il y a (1+len(texte_a)) × (1+len(texte_b)) cas à envisager.
En prenant encore une fois texte_a="LAPIN" et texte_b="CAPRIN", les différents cas envisagés apparaissent dans le tableau ci-dessous. On trouve dans chaque case la longueur de la plus longue sous-suite commune à chaque texte s'il s'arrêtait au caractère indiqué en début de ligne ou de colonne.
Ainsi, le 1 au bout de la double flèche est la longueur de la plus longue sous-suite commune aux textes "LA" et "CAPRI".
On constate que :
la première colonne et la première ligne du tableau ne contiennent que des 0. C'est en effet la longueur de la plus longue sous-suite commune dans le cas où l'un des textes est vide ;
si les derniers caractères considérés sont identiques, ce caractère commun fait partie de la sous-suite commune. On peut le supprimer et ajouter 1 au résultat de la case au dessus à gauche (flèche en diagonale);
si les derniers caractères considérés diffèrent, l'un des deux caractères (ou les deux) ne fait pas partie de la sous-suite commune. On compare les valeurs des cases de gauche et du dessus (flèches horizontale et verticale).
Version récursive
Cette fonction fait appel à la fonction récursive lplssc_rec qui prend en paramètres le nombre de caractères de chaque texte à comparer taille_a et taille_b. Cette fonction renvoie la longueur de la plus longue sous-suite commune aux taille_a premiers caractères de texte_a et aux taille_b premiers caractères de texte_b.
Par exemple, avec texte_a="LAPIN" et texte_b="CAPRIN", l'appel lplssc_rec(2,5) renvoie la longueur de la plus longue sous-suite commune à "LA" et "CAPRI".
On gardera trace des résultats intermédiaires dans un dictionnaire longueurs qui, à chaque couple (taille_a, taille_b), associe la longueur de la plus longue sous-suite commune.
La fonction étant récursive, on débutera par l'appel prenant en compte tous les caractères de chaque texte.
###(Dés-)Active le code après la ligne # Tests (insensible à la casse) (Ctrl+I)
Tronquer ou non le feedback dans les terminaux (sortie standard & stacktrace / relancer le code pour appliquer)
Si activé, le texte copié dans le terminal est joint sur une seule ligne avant d'être copié dans le presse-papier
Dans cette version itérative on détermine là encore les longueurs des plus longues sous-suites communes de toutes les versions de chaque texte.
On peut toutefois remarquer que les deux formules de récurrences (derniers caractères identiques ou différents) ne font intervenir que deux lignes à la fois. On peut donc compléter le tableau ligne par ligne en partant de la première et en ne gardant trace que de la dernière ligne complétée.
###(Dés-)Active le code après la ligne # Tests (insensible à la casse) (Ctrl+I)
Tronquer ou non le feedback dans les terminaux (sortie standard & stacktrace / relancer le code pour appliquer)
Si activé, le texte copié dans le terminal est joint sur une seule ligne avant d'être copié dans le presse-papier
# Tests(insensible à la casse)(Ctrl+I)