Cases remplies
Paires identiques
Plus longue jusqu'ici

  • En cours de remplissage
  • Lue
  • Réponse

En savoir plus sur la plus longue sous-séquence commune

Plus longue sous-séquence commune (LCS)

Quelles lettres deux mots ont-ils en commun, dans le même ordre ? La plus longue sous-séquence commune répond à cette question, et les outils diff, les correcteurs orthographiques et les comparaisons d'ADN s'appuient sur elle. Saisissez deux mots, regardez se remplir un tableau de leurs lettres, puis remontez jusqu'à la réponse depuis le coin. Appuyez sur Lecture pour voir le tableau se remplir, ou sur Étape et Retour pour avancer pas à pas. Faites glisser le curseur d'étapes pour aller n'importe où. Saisissez deux mots : le premier s'écrit le long du côté du tableau, le second le long du haut. Chaque case contient la longueur de la plus longue sous-séquence commune des lettres jusqu'à sa ligne et sa colonne. À la fin, les lettres sont relues à partir de la case en bas à droite. Nouvel exemple choisit une autre paire de mots. Quand le plateau est sélectionné, les flèches avancent ou reculent d'une étape, la barre d'espace lance et met en pause, et Origine et Fin vont au début et à la fin.

Comment ça marche

  1. Saisissez deux mots : le premier s'écrit le long du côté du tableau, le second le long du haut.
  2. Appuyez sur Lecture, ou utilisez Étape et Retour pour avancer pas à pas. Faites glisser le curseur d'étapes pour aller n'importe où.
  3. Regardez chaque case comparer ses deux lettres, puis suivez le chemin orange depuis le coin pour lire la réponse.

Comment fonctionne le tableau

Une case contient la longueur de la plus longue sous-séquence commune entre les lettres du premier mot jusqu'à sa ligne et celles du second mot jusqu'à sa colonne. La ligne et la colonne marquées – représentent un mot vide, elles valent donc 0. Si les deux lettres d'une case sont égales, la case vaut un de plus que la case en haut à gauche. Si elles diffèrent, l'une des deux lettres ne fait pas partie de la réponse, et la case prend la plus grande des valeurs de la case au-dessus et de la case à gauche.

Relire les lettres

La case en bas à droite donne la longueur de la réponse. Pour trouver les lettres, partez de là : quand les deux lettres sont identiques, cette lettre fait partie de la sous-séquence, et vous allez en haut à gauche ; sinon, vous allez vers la plus grande des cases au-dessus et à gauche. Les lettres recueillies en chemin, lues à l'envers, forment une plus longue sous-séquence commune. Il peut en exister d'autres de même longueur ; la relecture en trouve une.

Questions fréquemment posées

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

Une sous-chaîne est une suite de lettres côte à côte, comme ACE dans RACER. Une sous-séquence garde l'ordre mais peut sauter des lettres : ACE est donc aussi une sous-séquence de ABCDE. La plus longue sous-chaîne commune est un autre problème, avec un tableau semblable.

Quelle est la vitesse de l'algorithme LCS ?

Pour des mots de longueurs m et n, le tableau a m·n cases, chacune remplie en une étape : le travail est donc en O(m·n). Pour deux textes de 10 000 lignes, cela fait 100 millions de cases, c'est pourquoi les outils diff utilisent des méthodes plus astucieuses fondées sur la même idée.

La plus longue sous-séquence commune est-elle unique ?

Non. ABCBDAB et BDCABA ont trois sous-séquences communes différentes de longueur 4 : BCBA, BCAB et BDAB. Le tableau donne la longueur ; la relecture en choisit une.

La LCS indique-t-elle à quel point deux mots se ressemblent ?

En partie. Deux mots de longueurs m et n dont la plus longue sous-séquence commune a pour longueur k peuvent être transformés l'un en l'autre en supprimant m − k lettres et en en insérant n − k. La distance d'édition, qui permet aussi de remplacer une lettre, est souvent une meilleure mesure.

Des données sont-elles envoyées quelque part ?

Non. Tout est calculé dans votre navigateur, et vos derniers réglages restent dans le stockage local de ce navigateur.

Prêt à l'essayer ?

Ouvrez PictorX dans votre navigateur – aucune installation, aucune carte de crédit requise pour démarrer.

Aller à l'éditeur