Longest Common Subsequence

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

La solution par tableau s’exécute en temps O(n × m) , 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 a une complexité exponentielle.

MoyenProgrammation dynamique

+10

Vous recevez deux chaînes de caractères, 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 anglaises.

Exemples

Entrée: text1 = "stone"text2 = "longest"
Sortie: 3
Explication: o, n, e apparaissent dans cet ordre dans les deux mots, donc one est commun, longueur 3. Les lettres s et t viennent en dernier dans longest, mais en premier dans stone, donc les utiliser donne au plus st.

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.

Pour aller plus loin

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

Indices

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

0 sur 3 ouverts

Solution

L’appariement glouton échoue : apparier le c de cab avec le dernier c de abc ne laisse rien pour a et b ; l’ignorer permet de trouver ab. La réponse pour deux préfixes dépend des réponses pour des préfixes plus courts, donc un tableau (n+1) × (m+1) résout chaque paire une seule fois. Chaque ligne ne lit que la ligne au-dessus, donc deux lignes suffisent.

Compare les premières lettres avec la récursion

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:]. Si leurs premières lettres sont égales, associez-les : une plus longue sous-séquence commune qui ignore cette paire peut remplacer sa première paire par celle-ci sans raccourcir la 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, car leurs partenaires feraient se croiser les paires. On peut donc en supprimer une : max(lcs(i+1, j), lcs(i, j+1)). Un suffixe vide donne 0.

Chaque différence déclenche deux appels. Deux chaînes de 20 lettres sans aucune lettre en commun nécessitent déjà environ 2.8 × 10^11 appels, alors qu’il n’existe que (n+1) × (m+1) paires différentes (i, j) : presque chaque appel répète donc 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)

Remplir un tableau de préfixes

Intuition

Soit dp[i][j] la réponse pour les i premières lettres de text1 et les j premières lettres de text2 : l’indice 0 désigne donc un préfixe vide, et la ligne 0 ainsi que la colonne 0 valent 0. Comparez les dernières lettres des deux préfixes, text1[i-1] et text2[j-1] : si elles sont égales, elles s’associent, dp[i-1][j-1] + 1 ; si elles sont différentes, on en élimine une, max(dp[i-1][j], dp[i][j-1]). C’est la récurrence lue depuis la fin.

Chaque cellule lit les cellules au-dessus, à gauche et en diagonale en haut à gauche, donc en remplissant ligne par ligne, de gauche à droite, elles sont toujours déjà calculées. Pour pear et reap, la ligne correspondant à pea est [0, 0, 1, 2, 2] ; sa cellule correspondant à rea vaut 2, car a correspond à a, ce qui ajoute un à la cellule correspondant à pe et re.

Deux chaînes de 1000 lettres nécessitent environ 10^6 étapes à temps constant.

Algorithme

Crée un tableau dp de zéros de dimensions (n+1) × (m+1).
Pour i de 1 à n et j de 1 à m, compare text1[i-1] avec text2[j-1].
En cas de correspondance, définis dp[i][j] = dp[i-1][j-1] + 1.
Sinon, définis dp[i][j] = max(dp[i-1][j], dp[i][j-1]).
Retourne 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 garder que deux lignes

Intuition

Une fois qu’une ligne est terminée, les lignes au-dessus ne sont plus jamais lues. Garde prev pour la ligne terminée et cur pour la ligne en cours de remplissage, puis échange-les après chaque ligne. La récurrence et l’ordre restent les mêmes.

La réponse ne dépend pas de la chaîne qui vient en premier : fais donc 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 les mêmes 10^6 étapes.

Algorithme

Si text2 est plus long que text1, permute-les.
Crée prev et cur, chacun contenant m + 1 zéros, où m est la longueur la plus courte.
Pour chaque lettre de text1, remplis cur[1..m] avec la même règle que dans le tableau, en lisant prev pour la ligne du 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

Mélanger les indices de la table avec les indices de chaîne. La cellule dp[i][j] compare text1[i-1] avec 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.
Écrire dans la ligne depuis laquelle vous êtes encore en train de lire. Avec deux lignes, chaque valeur de la ligne précédente doit provenir de prev, et cur[0] doit rester à 0.
Mémoriser la récursion en Python avec des chaînes de 1000 lettres. La profondeur d’appel atteint 2000, dépassant la limite par défaut de 1000.

Questions fréquentes3

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

La solution par tableau s’exécute en temps O(n × m), 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 a une complexité 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 ignorer des lettres tant que l’ordre est conservé ; 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). Le tableau des sous-chaînes réinitialise une cellule à 0 en cas de différence, au lieu de recopier une cellule voisine.

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

Un diff entre deux versions d’un fichier conserve la plus longue sous-séquence commune de leurs lignes et indique toutes les autres lignes comme ajoutées ou supprimées. 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 nécessite donc son propre tableau.

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

Test #1

Test #2

Test #3

Arguments

text1 = "stone"
text2 = "longest"

Résultat attendu

Longest Common Subsequence

Fonction

Contraintes

Exemples

Indices

Solution

Compare les premières lettres avec la récursion

Remplir un tableau de préfixes

Ne garder que deux lignes

Pièges et cas limites

Questions fréquentes3

Problèmes similaires