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à3de'lapin'ce qui donne'lapi', -
on travaille avec les lettres d'indice
0à4de'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
>>> lplsc('lapin', 'caprin')
4
>>> lplsc('abcd', 'abcde')
4
>>> 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-nlNone
A
Z