Longest Common Substring

Q: Quelle est la complexité temporelle de la plus longue sous-chaîne commune ?

La solution par programmation dynamique prend un temps de O(n × m) et nécessite O(m) mémoire avec une seule ligne. Étendre à partir de chaque paire de débuts prend O(n × m × min(n, m)) dans le pire des cas. Un automate des suffixes atteint environ O(n + m) , au prix d’un programme beaucoup plus long.

Q: Comment renvoyer la plus longue sous-chaîne commune elle-même ?

Chaque fois qu’une cellule dépasse best , enregistre aussi la position i dans s1 où ce bloc se termine. À la fin, la sous-chaîne correspond aux lettres de s1 qui se terminent à cet endroit et dont la longueur est égale à best . Une comparaison strictement supérieure permet de conserver le premier bloc le plus long trouvé dans s1 .

MoyenProgrammation dynamique

+10

On te donne deux chaînes, s1 et s2. Une sous-chaîne est une suite ininterrompue de lettres tirées d’une chaîne, comme ork dans clockwork. Trouve la plus longue sous-chaîne commune à s1 et s2, puis retourne sa longueur. Si aucune lettre n’apparaît dans les deux chaînes, la réponse est 0.

Fonction

longestCommonSubstring(s1: string, s2: string) → integer

s1string: la première chaîne
s2string: la deuxième chaîne
Renvoieinteger: la longueur du plus long bloc de lettres présent dans les deux chaînes

Contraintes

1 ≤ s1.length ≤ 1000
1 ≤ s2.length ≤ 1000
s1 et s2 sont composés de lettres minuscules anglaises.

Exemples

Entrée: s1 = "clockwork"s2 = "workshop"
Sortie: 4
Explication: work se trouve à la fin de clockwork et au début de workshop : c’est donc une sous-chaîne commune de longueur 4, et aucun bloc plus long n’apparaît dans les deux.

Entrée: s1 = "hammer"s2 = "harmed"
Sortie: 2
Explication: ha et me apparaissent dans les deux mots, mais aucune suite de trois lettres n’y apparaît. Les deux mots contiennent h, a, m, e dans cet ordre, mais harmed comporte un r entre le a et le m.

Pour aller plus loin

Peux-tu vérifier si une sous-chaîne commune de longueur donnée L existe en environ O(n + m) avec un hachage roulant, puis effectuer une recherche dichotomique sur L ?

Indices

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

0 sur 3 ouverts

Solution

Étendre une correspondance à partir de chaque paire de positions de départ relit les mêmes lettres. Regardez plutôt où un bloc se termine : le bloc commun qui se termine à s1[i] et s2[j] est plus long d’une lettre que celui qui se termine aux deux lettres qui les précèdent, ou est vide si les lettres diffèrent. Un tableau de ces longueurs donne la réponse en O(n × m) temps.

Étendez à partir de chaque paire de positions de départ

Correcte, mais ne termine pas sur les plus gros tests

Intuition

Chaque sous-chaîne commune commence à une position i de s1 et à une position j de s2. Pour chaque paire, avancez tant que les lettres concordent et comptez les étapes ; le plus grand nombre obtenu est la réponse.

Les textes répétitifs allongent les parcours. Lorsque les deux chaînes contiennent 1000 copies de a, chaque paire avance jusqu’à la fin du suffixe le plus court : environ 3.3 × 10^8 comparaisons de lettres. Le parcours à partir de (i, j) répète entièrement le parcours à partir de (i+1, j+1), une lettre plus loin.

Algorithme

Définissez best = 0.
Pour chaque i dans s1 et chaque j dans s2, définissez k = 0.
Tant que i+k et j+k sont tous deux dans leurs chaînes respectives et que s1[i+k] == s2[j+k], ajoutez 1 à k.
Conservez la plus grande valeur de k dans best, puis renvoyez-la.

def longestCommonSubstring(s1, s2):
    n, m = len(s1), len(s2)
    best = 0
    for i in range(n):
        for j in range(m):
            # Walk forward while the two strings agree
            k = 0
            while i + k < n and j + k < m and s1[i + k] == s2[j + k]:
                k += 1
            if k > best:
                best = k
    return best

Tableau des longueurs de blocs qui se terminent à chaque paire

Intuition

Soit run[i][j] la longueur du plus long bloc commun qui se termine exactement à s1[i-1] et s2[j-1] ; la ligne 0 et la colonne 0 contiennent 0. Un tel bloc doit contenir les deux lettres. Si elles diffèrent, aucun bloc n’existe et la cellule vaut 0. Si elles correspondent, le bloc est cette paire plus le bloc se terminant une lettre plus tôt dans les deux chaînes : run[i-1][j-1] + 1. Chaque sous-chaîne commune se termine quelque part ; la réponse est donc la plus grande cellule, où qu’elle se trouve.

Pour hammer et harmed, les h donnent 1 et les a prolongent le bloc jusqu’à 2, puis le r interrompt le bloc. Le deuxième m de hammer rencontre le m de harmed après une différence entre m et r ; il commence donc à 1, et les e le portent à 2. Aucune cellule n’atteint 3.

Une comparaison par cellule : environ un million pour deux chaînes de 1000 lettres, quel que soit le texte.

Algorithme

Initialisez run avec n+1 lignes et m+1 colonnes, toutes à 0, et définissez best = 0.
Parcourez i de 1 à n et, à l’intérieur, j de 1 à m, en comparant s1[i-1] à s2[j-1].
En cas de correspondance, définissez run[i][j] = run[i-1][j-1] + 1 et mettez à jour best.
En cas de non-correspondance, laissez la cellule à 0.
Retournez best.

def longestCommonSubstring(s1, s2):
    n, m = len(s1), len(s2)
    # run[i][j]: length of the longest block that ends at s1[i-1] and at s2[j-1]
    run = [[0] * (m + 1) for _ in range(n + 1)]
    best = 0
    for i in range(1, n + 1):
        for j in range(1, m + 1):
            if s1[i - 1] == s2[j - 1]:
                run[i][j] = run[i - 1][j - 1] + 1
                if run[i][j] > best:
                    best = run[i][j]
            # a mismatch leaves run[i][j] at 0
    return best

Une ligne, mise à jour de droite à gauche

Intuition

Chaque cellule ne lit que la cellule située en diagonale en haut à gauche. Ainsi, un seul tableau run de m+1 nombres peut contenir le tableau si tu parcours j de droite à gauche : lorsque tu écris run[j], l’emplacement run[j-1] contient encore la valeur de la lettre précédente de s1, qui est la cellule diagonale.

En cas de non-correspondance, il faut maintenant écrire explicitement 0, car l’emplacement contient encore un nombre de la ligne précédente. La complexité temporelle reste O(n × m), et la mémoire passe d’environ 10^6 nombres à 1001.

Algorithme

Crée un tableau run de m+1 zéros et définis best = 0.
Pour chaque lettre ch de s1, parcours j de m à 1 en descendant.
Si ch == s2[j-1], définis run[j] = run[j-1] + 1 et mets à jour best.
Sinon, définis run[j] = 0.
Renvoie best.

def longestCommonSubstring(s1, s2):
    m = len(s2)
    # run[j]: length of the common block that ends at the current letter of s1 and at s2[j-1]
    run = [0] * (m + 1)
    best = 0
    for ch in s1:
        # Right to left, so run[j-1] still holds the value from the previous letter of s1
        for j in range(m, 0, -1):
            if ch == s2[j - 1]:
                run[j] = run[j - 1] + 1
                if run[j] > best:
                    best = run[j]
            else:
                run[j] = 0
    return best

Pièges et cas limites

Retourner la dernière cellule. run[n][m] ne couvre que les blocs qui se terminent à la dernière lettre des deux chaînes. Pour abc et abd, le résultat est 0, tandis que pour ab, il est 2.
Copier le voisin le plus grand en cas de différence. C’est la règle de la sous-séquence, qui permet à un bloc de sauter des lettres : pour hammer et harmed, elle renvoie 4 au lieu de 2.
Parcourir la ligne unique de gauche à droite. La valeur diagonale est écrasée avant d’être lue, donc a comparé à aa donne 2.
Omettre la réinitialisation dans la ligne unique. Une longueur correspondant à la lettre précédente de s1 est conservée et prolonge ensuite un bloc qui n’existe pas.
Parcourir la méthode par force brute sans vérifier les limites. Pour zzzz comparé à zz, le programme lit au-delà de la fin de la chaîne la plus courte.

Questions fréquentes3

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

Une sous-chaîne est une suite ininterrompue de lettres ; une sous-séquence conserve l’ordre, mais peut comporter des espaces. Pour hammer et harmed, la plus longue sous-chaîne commune a une longueur de 2 et la plus longue sous-séquence commune a une longueur de 4 (hame). Dans les tableaux, une différence remet la cellule de la sous-chaîne à 0, mais fait que la cellule de la sous-séquence copie son voisin le plus grand.

Quelle est la complexité temporelle de la plus longue sous-chaîne commune ?

La solution par programmation dynamique prend un temps de O(n × m) et nécessite O(m) mémoire avec une seule ligne. Étendre à partir de chaque paire de débuts prend O(n × m × min(n, m)) dans le pire des cas. Un automate des suffixes atteint environ O(n + m), au prix d’un programme beaucoup plus long.

Comment renvoyer la plus longue sous-chaîne commune elle-même ?

Chaque fois qu’une cellule dépasse best, enregistre aussi la position i dans s1 où ce bloc se termine. À la fin, la sous-chaîne correspond aux lettres de s1 qui se terminent à cet endroit et dont la longueur est égale à best. Une comparaison strictement supérieure permet de conserver le premier bloc le plus long trouvé dans s1.

def longestCommonSubstring(s1, s2):
    # Écrivez le code ici

Test #1

Test #2

Test #3

Arguments

s1 = "clockwork"
s2 = "workshop"

Résultat attendu

Longest Common Substring

Fonction

Contraintes

Exemples

Indices

Solution

Étendez à partir de chaque paire de positions de départ

Tableau des longueurs de blocs qui se terminent à chaque paire

Une ligne, mise à jour de droite à gauche

Pièges et cas limites

Questions fréquentes3

Problèmes similaires