Plus longue sous-séquence commune

Un article de Wikipédia, l'encyclopédie libre.
Aller à : navigation, rechercher
image illustrant l’informatique
Cet article est une ébauche concernant l’informatique.

Vous pouvez partager vos connaissances en l’améliorant (comment ?) selon les recommandations des projets correspondants.

 Ne doit pas être confondu avec plus longue sous-chaîne commune.

La plus longue sous-séquence commune à deux suites, ou deux chaînes de caractère, est une séquence étant sous-suite des deux suites, et étant de taille maximum. La résolution de ce problème peut être obtenue par programmation dynamique.

Exemple[modifier | modifier le code]

Pour les deux séquences de caractères suivantes :

  • « abcde »,
  • « ceij »,

la plus longue sous-séquence commune est « ce ».

Dans ce problème, il est nécessaire que les éléments communs soient dans le même ordre dans les différentes séquences, mais pas qu’ils soient obligatoirement consécutifs : « e » n’est pas consécutif à « c » dans la première séquence.

Algorithme[modifier | modifier le code]

Une telle sous-séquence peut être obtenue par un algorithme de programmation dynamique dont le temps d'exécution est proportionnel au produit des longueurs des deux séquences[1].

La généralisation à un nombre arbitraire de suites est un problème NP-difficile. Le temps d'exécution de l'algorithme est exponentiel en le nombre de séquences.

Notes et références[modifier | modifier le code]

Voir aussi[modifier | modifier le code]