Longest Common Subsequence

Q: Quelle est la complexité temporelle de la plus longue sous-séquence commune ?

La solution avec tableau s’exécute en O(n × m) , où n et m sont les deux longueurs : elle remplit une cellule par paire de préfixes. Elle nécessite O(n × m) de mémoire pour le tableau complet, ou O(min(n, m)) avec deux lignes. La récursion simple sans tableau est exponentielle.

Q: Comment afficher la plus longue sous-séquence commune elle-même ?

Remplissez le tableau entier, puis remontez à partir de dp[n][m] . Lorsque les deux lettres de la cellule courante correspondent, cette lettre fait partie de la réponse : notez-la et avancez en diagonale vers le haut et la gauche. Sinon, avancez vers le voisin du dessus ou de gauche qui contient la valeur la plus élevée. Inversez les lettres notées à la fin. La version à deux lignes ne peut pas faire cela, car elle a supprimé les lignes précédentes.

MoyenProgrammation dynamique

+10

Vous recevez deux chaînes, text1 et text2. Une sous-séquence d’une chaîne conserve certaines de ses lettres dans leur ordre d’origine et supprime les autres ; les lettres conservées n’ont pas besoin d’être voisines. Renvoyez la longueur de la plus longue chaîne qui est une sous-séquence des deux, ou 0 si les deux chaînes n’ont aucune lettre en commun.

Fonction

longestCommonSubsequence(text1: string, text2: string) → integer

text1string: la première chaîne
text2string: la deuxième chaîne
Renvoieinteger: la longueur de la plus longue sous-séquence commune

Contraintes

1 ≤ text1.length ≤ 1000
1 ≤ text2.length ≤ 1000
Les deux chaînes contiennent uniquement des lettres minuscules de l’alphabet anglais.

Exemples

Entrée: text1 = "stone"text2 = "longest"
Sortie: 3
Explication: o, n et e apparaissent dans cet ordre dans les deux mots, donc one est une sous-séquence commune de longueur 3. Dans longest, les lettres s et t viennent en dernier, tandis que dans stone, elles viennent en premier. Une sous-séquence commune qui les utilise ne peut donc être que st, qui est plus courte.

Entrée: text1 = "pear"text2 = "reap"
Sortie: 2
Explication: ea apparaît dans les deux mots. Le p et le r se trouvent de part et d’autre de ea dans les deux mots, donc aucun des deux ne peut s’y joindre, et la réponse est 2.

+19 tests cachés à la soumission

Pour aller plus loin

Peux-tu renvoyer une plus longue sous-séquence commune elle-même, et pas seulement sa longueur ?

Indices

Ouvrez-les un par un. Chacun en dévoile un peu plus.

0 sur 3 ouverts

Solution

Faire correspondre les lettres de manière gloutonne ne fonctionne pas. Une lettre peut correspondre à plusieurs positions dans l’autre chaîne, et la première correspondance peut empêcher d’en trouver de meilleures : associer le c de cab au c à la fin de abc ne laisse rien pour a et b, tandis que l’ignorer permet de trouver ab. L’idée qui résout le problème, c’est que la réponse pour deux préfixes dépend uniquement des réponses pour des préfixes légèrement plus courts. Un tableau de (n+1) × (m+1) nombres résout chaque paire une seule fois et, comme chaque ligne ne lit que la ligne du dessus, deux lignes suffisent.

Comparer les premières lettres avec la récursivité

Correcte, mais ne termine pas sur les plus gros tests

Intuition

Soit lcs(i, j) la réponse pour les suffixes text1[i:] et text2[j:]. Regardons leurs premières lettres. Si elles sont égales, associons-les : une plus longue sous-séquence commune qui n’utilise pas cette paire peut remplacer sa première paire par celle-ci sans raccourcir la sous-séquence. La réponse est donc 1 + lcs(i+1, j+1).

Si les lettres diffèrent, elles ne peuvent pas être utilisées toutes les deux, puisque chacune ne pourrait être associée qu’à une lettre ultérieure de l’autre chaîne, et les paires se croiseraient. On peut donc supprimer l’une d’elles : la réponse est max(lcs(i+1, j), lcs(i, j+1)). Lorsque l’un des suffixes est vide, rien n’est commun et la réponse est 0.

C’est lent parce que chaque différence déclenche deux appels. Si les chaînes n’ont aucune lettre en commun, chaque appel rencontre une différence jusqu’à ce que l’une des chaînes soit épuisée, et le nombre d’appels croît comme le nombre de façons d’entrelacer les deux chaînes. Pour deux chaînes de 20 lettres, cela représente environ 2.8 × 10^11 appels ; les grands tests contiennent 1000 lettres chacune. Pourtant, il n’existe que (n+1) × (m+1) paires (i, j) différentes, donc presque chaque appel répète un appel précédent.

Algorithme

Écris lcs(i, j) pour les suffixes commençant à i et j.
Si i ou j dépasse la fin de sa chaîne, renvoie 0.
Si text1[i] == text2[j], renvoie 1 + lcs(i+1, j+1).
Sinon, renvoie max(lcs(i+1, j), lcs(i, j+1)).
La réponse est lcs(0, 0).

def longestCommonSubsequence(text1, text2):
    def lcs(i, j):
        # The longest common subsequence of text1[i:] and text2[j:]
        if i == len(text1) or j == len(text2):
            return 0
        if text1[i] == text2[j]:
            return 1 + lcs(i + 1, j + 1)
        return max(lcs(i + 1, j), lcs(i, j + 1))

    return lcs(0, 0)

Remplissez un tableau de préfixes

Intuition

État. Soit dp[i][j] la plus longue sous-séquence commune des i premières lettres de text1 et des j premières lettres de text2. Travailler avec des préfixes permet à l’indice 0 de désigner une chaîne vide.

Récurrence. Comparez les dernières lettres des deux préfixes, text1[i-1] et text2[j-1]. Si elles sont égales, associez-les : dp[i][j] = dp[i-1][j-1] + 1. Sinon, éliminez l’une d’elles : dp[i][j] = max(dp[i-1][j], dp[i][j-1]). C’est le même raisonnement que pour la récursion, en partant de la fin. Cas de base : la ligne 0 et la colonne 0 valent 0, car un préfixe vide n’a rien en commun avec quoi que ce soit. Ordre : chaque cellule lit celle située au-dessus, celle à sa gauche et celle en diagonale en haut à gauche ; ainsi, en remplissant ligne par ligne, de gauche à droite, elles sont toujours déjà calculées. La réponse est dp[n][m].

Pour pear et reap, la ligne correspondant à pea est [0, 0, 1, 2, 2]. Sa cellule correspondant à rea vaut 2, car a correspond à a ; elle vaut donc 1, la valeur de la cellule correspondant à pe et re, plus un. La dernière cellule, pour pear face à reap, compare r à p, qui sont différentes, et prend la plus grande valeur de ses deux voisines, soit 2.

Le tableau contient (n+1) × (m+1) cellules et chacune nécessite un temps constant : environ 10^6 étapes pour deux chaînes de 1000 lettres. Une version mémoïsée de la récursion remplit les mêmes cellules, mais elle récursive jusqu’à une profondeur de n + m appels, ce qui provoque un dépassement de la pile d’appels par défaut dans des langages comme Python.

Algorithme

Créez une table dp de zéros de dimensions (n+1) × (m+1).
Pour i de 1 à n et j de 1 à m, comparez text1[i-1] à text2[j-1].
En cas de correspondance, définissez dp[i][j] = dp[i-1][j-1] + 1.
Sinon, définissez dp[i][j] = max(dp[i-1][j], dp[i][j-1]).
Renvoyez dp[n][m].

def longestCommonSubsequence(text1, text2):
    n, m = len(text1), len(text2)
    # dp[i][j]: the longest common subsequence of text1[:i] and text2[:j].
    # Row 0 and column 0 stay 0: an empty prefix has nothing in common.
    dp = [[0] * (m + 1) for _ in range(n + 1)]
    for i in range(1, n + 1):
        for j in range(1, m + 1):
            if text1[i - 1] == text2[j - 1]:
                dp[i][j] = dp[i - 1][j - 1] + 1
            else:
                dp[i][j] = max(dp[i - 1][j], dp[i][j - 1])
    return dp[n][m]

Ne conserver que deux lignes

Intuition

La ligne i du tableau ne lit que la ligne i-1 et ses propres cellules précédentes. Une fois qu’une ligne est terminée, on ne relit plus jamais les lignes au-dessus. Il suffit donc de conserver deux tableaux, prev pour la ligne terminée et cur pour la ligne en cours de remplissage, puis de les échanger après chaque ligne. La récurrence et l’ordre restent exactement les mêmes.

Une sous-séquence commune à deux chaînes ne dépend pas de l’ordre des chaînes : tu peux donc les échanger et faire défiler les lignes le long de la plus courte. Chaque ligne contient alors min(n, m) + 1 nombres : 1001 au lieu d’un million de cellules pour les entrées les plus grandes, avec le même nombre de 10^6 étapes de calcul.

La première entrée de chaque ligne représente un préfixe vide de la chaîne la plus courte ; elle doit donc rester à 0. La réponse est la dernière entrée de la dernière ligne terminée.

Algorithme

Si text2 est plus long que text1, permute-les.
Crée prev et cur, contenant chacun m + 1 zéros, où m est la longueur la plus courte.
Pour chaque lettre de text1, remplis cur[1..m] en appliquant la même règle que dans le tableau, en lisant prev pour la ligne au-dessus.
Permute prev et cur.
Renvoie prev[m].

def longestCommonSubsequence(text1, text2):
    if len(text2) > len(text1):
        text1, text2 = text2, text1  # keep the rows as short as the shorter string
    m = len(text2)
    # prev[j]: the answer for the previous prefix of text1 and text2[:j]
    prev = [0] * (m + 1)
    for ch in text1:
        cur = [0] * (m + 1)
        for j in range(1, m + 1):
            if ch == text2[j - 1]:
                cur[j] = prev[j - 1] + 1
            else:
                cur[j] = max(prev[j], cur[j - 1])
        prev = cur
    return prev[m]

Pièges et cas limites

La relation de récurrence est courte, et la plupart des bogues sont dus à un décalage d’une unité ou à l’ajout d’une correspondance au mauvais endroit.

Confondre les indices du tableau avec ceux des chaînes. La cellule dp[i][j] compare text1[i-1] à text2[j-1], car la ligne 0 correspond au préfixe vide.
En cas de correspondance, ajouter un à max(dp[i-1][j], dp[i][j-1]) au lieu de l’ajouter à dp[i-1][j-1]. Cela peut utiliser deux fois la même lettre : aa comparé à a renverrait 2 au lieu de 1.
Faire une correspondance gloutonne avec deux pointeurs. cab comparé à abc associe les deux lettres c et renvoie 1, alors que ab donne 2.
Écrire dans la ligne que vous êtes en train de lire. Avec deux lignes, chaque valeur de la ligne précédente doit provenir de prev, et cur[0] doit rester égal à 0.
Résoudre par erreur le problème de la plus longue sous-chaîne commune. Une sous-séquence peut ignorer des lettres ; une sous-chaîne ne le peut pas.
Mémoriser les résultats avec une récursion sur des chaînes de 1000 lettres. La profondeur des appels atteint 2000, ce qui dépasse la limite par défaut de 1000 de Python.

Questions fréquentes4

Quelle est la complexité temporelle de la plus longue sous-séquence commune ?

La solution avec tableau s’exécute en O(n × m), où n et m sont les deux longueurs : elle remplit une cellule par paire de préfixes. Elle nécessite O(n × m) de mémoire pour le tableau complet, ou O(min(n, m)) avec deux lignes. La récursion simple sans tableau est exponentielle.

Quelle est la différence entre la plus longue sous-séquence commune et la plus longue sous-chaîne commune ?

Une sous-séquence peut sauter des lettres tant que leur ordre est conservé, tandis qu’une sous-chaîne est un bloc de lettres voisines. Pour stone et longest, la plus longue sous-séquence commune est one (3), mais la plus longue sous-chaîne commune est on (2). La version avec les sous-chaînes utilise un tableau similaire, mais une différence réinitialise la cellule à 0 au lieu de recopier une cellule voisine.

Comment afficher la plus longue sous-séquence commune elle-même ?

Remplissez le tableau entier, puis remontez à partir de dp[n][m]. Lorsque les deux lettres de la cellule courante correspondent, cette lettre fait partie de la réponse : notez-la et avancez en diagonale vers le haut et la gauche. Sinon, avancez vers le voisin du dessus ou de gauche qui contient la valeur la plus élevée. Inversez les lettres notées à la fin. La version à deux lignes ne peut pas faire cela, car elle a supprimé les lignes précédentes.

Quel est le lien entre le LCS, les outils diff et la distance d’édition ?

Une comparaison entre deux versions d’un fichier trouve la plus longue sous-séquence commune de leurs lignes ; chaque ligne qui n’en fait pas partie est affichée comme ajoutée ou supprimée. De la même façon, le nombre minimal d’insertions et de suppressions nécessaires pour transformer une chaîne en l’autre est n + m - 2 × LCS. La distance d’édition permet aussi de remplacer une lettre ; elle utilise donc son propre tableau, avec un troisième choix par cellule.

Python

def longestCommonSubsequence(text1, text2):
    # Écrivez le code ici

Cas de test

Cas 1

Cas 2

Cas 3

Entrée

text1 = "stone"
text2 = "longest"

Attendu

Longest Common Subsequence

Fonction

Contraintes

Exemples

Indices

Solution

Comparer les premières lettres avec la récursivité

Remplissez un tableau de préfixes

Ne conserver que deux lignes

Pièges et cas limites

Questions fréquentes4

Problèmes similaires