Aller au contenu

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 :

  1. L'un des deux textes est de longueur nulle,

  2. Le dernier caractère dans chaque texte est identique,

  3. Le dernier caractère des deux textes est différent.

Coup de pouce 2

Dans les trois cas :

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

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

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

###
# Tests supplémentairesbksl-nltextepy-unda = "bertrand roule en vélo"bksl-nltextepy-undb = "bravo"bksl-nlassert lplsc(textepy-unda, textepy-undb) == 5bksl-nlbksl-nlbksl-nltextepy-unda = "resulta"bksl-nltextepy-undb = "résultats"bksl-nlassert lplsc(textepy-unda, textepy-undb) == 6bksl-nlbksl-nlbksl-nltextepy-unda = "résultats"bksl-nltextepy-undb = "résultats"bksl-nlassert lplsc(textepy-unda, textepy-undb) == 9bksl-nlbksl-nlbksl-nltextepy-unda = "résultats"bksl-nltextepy-undb = ""bksl-nlassert lplsc(textepy-unda, textepy-undb) == 0bksl-nlbksl-nl ∞/∞

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

Retour en haut de la page