Longueur des plus longues sous-chaines⚓︎

Objectif⚓︎

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-chaine commune à ces deux textes ?

Définition

On appelle sous-chaine d'une chaine de caractères, une chaine produite en enlevant zéro, un ou plusieurs caractères.

Par exemple, 'an' est une sous-chaine de 'lapin'.

'an' est aussi une sous-chaine commune à 'lapin' et 'caprin'.

Dans certains cas, il peut y avoir plusieurs sous-chaines communes de longueurs identiques. Par exemple les chaines 'abc' et 'bac' admettent deux sous-chaines communes de longueur 2 : 'ac' et 'bc'.

On va donc plutôt calculer la longueur de la plus longue sous-chaine 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-chaine commune est donc 'apin'. Elle est de longueur 4.

Au travail !⚓︎

Compléter la fonction lplsc (pour longueur plus longue sous-chaine) ci-dessous.

Cette fonction prend en argument les deux textes à comparer (texte_a et texte_b) et renvoie la longueur de la plus longue sous-chaine commune.

Cette fonction fait appel à la fonction récursive lplsc_rec prenant en argument les indices i_a et i_b des derniers caractères à considérer dans texte_a et texte_b. Cette fonction renvoie la longueur de la plus longue sous-chaine commune.

Par exemple, avec texte_a = 'lapin' et texte_b = 'caprin', l'appel lplsc_rec(3, 4) renvoie la longueur de la plus longue sous-chaine commune à 'lapi' et 'capri'. En effet,

on travaille avec les lettres d'indice 0 à 3 de 'lapin' ce qui donne 'lapi',
on travaille avec les lettres d'indice 0 à 4 de 'caprin' ce qui donne 'capri'.

On gardera trace des résultats intermédiaires dans un dictionnaire memoire qui à chaque couple (i_a, i_b) associe la longueur de la plus longue sous-chaine commune.

Exemples

🐍 Console Python

>>> lplsc('lapin', 'caprin')
4

🐍 Console Python

>>> lplsc('abcd', 'abcde')
4

🐍 Console Python

>>> lplsc('aBaBaBaB', 'aaa')
3

Coup de pouce 1

On peut lire les deux textes de droite à gauche.

Trois cas se présentent à nous :

L'un des deux textes est de longueur nulle,
Le dernier caractère dans chaque texte est identique,
Le dernier caractère des deux textes est différent.

Coup de pouce 2

Dans les trois cas :

Si l'un des textes est de longueur nulle, l'indice du dernier caractère prend une valeur absurde et la plus longue sous-chaine commune est de longueur nulle.
Si le dernier caractère est identique, il fera nécessairement partie de la sous-chaine commune. On peut réduire la taille du problème...
Si les derniers caractères sont différents, l'un ou l'autre ne fait pas partie de la plus longue sous-chaine commune. On essaie les deux situations et l'on conserve la meilleure.

###

∞/∞

def lplsc(textepy-unda, textepy-undb):bksl-nlbksl-nl def lplscpy-undrec(ipy-unda, ipy-undb):bksl-nl if ipy-unda == ... or ...:bksl-nl return ...bksl-nl if (ipy-unda, ipy-undb) ...:bksl-nl if textepy-unda[ipy-unda] == ...:bksl-nl memoire[...] = 1 + ...bksl-nl else:bksl-nl memoire[...] = ...bksl-nlbksl-nl return ...bksl-nlbksl-nl ipy-unda = ...bksl-nl ipy-undb = ...bksl-nl memoire = ...bksl-nl return lplscpy-undrec(..., ...)bksl-nlbksl-nlbksl-nl# Testsbksl-nltextepy-unda = "lapin"bksl-nltextepy-undb = "caprin"bksl-nlassert lplsc(textepy-unda, textepy-undb) == 4bksl-nlbksl-nltextepy-unda = "abcd"bksl-nltextepy-undb = "abcde"bksl-nlassert lplsc(textepy-unda, textepy-undb) == 4bksl-nlbksl-nltextepy-unda = "aBaBaBaB"bksl-nltextepy-undb = "aaa"bksl-nlassert lplsc(textepy-unda, textepy-undb) == 3bksl-nlbksl-nldef lplsc(textepy-unda, textepy-undb):bksl-nlbksl-nl def lplscpy-undrec(ipy-unda, ipy-undb):bksl-nl if ipy-unda == -1 or ipy-undb == -1:bksl-nl return 0bksl-nl if (ipy-unda, ipy-undb) not in memoire:bksl-nl if textepy-unda[ipy-unda] == textepy-undb[ipy-undb]:bksl-nl memoire[(ipy-unda, ipy-undb)] = 1 + lplscpy-undrec(ipy-unda - 1,bksl-nl ipy-undb - 1)bksl-nl else:bksl-nl memoire[(ipy-unda, ipy-undb)] = max(lplscpy-undrec(ipy-unda - 1, ipy-undb),bksl-nl lplscpy-undrec(ipy-unda, ipy-undb - 1))bksl-nl return memoire[(ipy-unda, ipy-undb)]bksl-nlbksl-nl ipy-unda = len(textepy-unda) - 1bksl-nl ipy-undb = len(textepy-undb) - 1bksl-nl memoire = {}bksl-nl return lplscpy-undrec(ipy-unda, ipy-undb)bksl-nlbksl-nlbksl-nl# Testsbksl-nltextepy-unda = "lapin"bksl-nltextepy-undb = "caprin"bksl-nlassert lplsc(textepy-unda, textepy-undb) == 4bksl-nlbksl-nltextepy-unda = "abcd"bksl-nltextepy-undb = "abcde"bksl-nlassert lplsc(textepy-unda, textepy-undb) == 4bksl-nlbksl-nltextepy-unda = "aBaBaBaB"bksl-nltextepy-undb = "aaa"bksl-nlassert lplsc(textepy-unda, textepy-undb) == 3bksl-nlbksl-nl

Dans la fonction principale on détermine la longueur de chaque chaine avant de créer le dictionnaire memoire initialement vide. On initie ensuite les appels récursifs en faisant lplsc_rec(i_a, i_b).

Comme la sous-fonction est récursive, il est bon de débuter par un cas de base. C'est ici le cas ou l'un des deux textes est de longueur nulle. On teste ce cas en observant le rang du dernier caractère à étudier : s'il est négatif, c'est que la chaine est vide (on a soustrait 1 une fois de trop à i_a ou i_b). Dans ce cas, on renvoie directement 0.

On vérifie ensuite que le cas a été traité ou non. Pour cela on se demande si la clé (i_a, i_b) n'est pas présente dans le dictionnaire memoire.

Si c'est le cas, il faut traiter cette comparaison :

si les derniers caractères sont identiques, on passe aux caractères précédents et l'on ajoute 1 au résultat. Cette valeur est immédiatement stockée dans le dictionnaire memoire,
si les caractères diffèrent, on étudie les deux cas précisés par l'énoncé. On place dans le dictionnaire le résultat le plus grand.

En dernier lieu, on renvoie la valeur que l'on vient d'insérer dans le dictionnaire.