Plus longue sous-séquence commune

Un article de Wikipédia, l'encyclopédie libre.
Aller à : navigation, rechercher

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]

  1. Thomas H. Cormen, Charles E. Leiserson, Ronald L. Rivest et Clifford Stein, Introduction à l’algorithmique, Dunod,‎ , 2e éd., 1146 p. [détail de l’édition] (ISBN 2-10-003922-9), chapitre 15.4, pages 345.

Voir aussi[modifier | modifier le code]