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
>>> 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