Plus longue sous-séquence commune

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

La détermination de la plus longue sous-séquence commune à différentes (super-) séquences est un problème NP-complet difficile.

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.

Informatique[modifier | modifier le code]

La résolution de ce problème peut être obtenue par programmation dynamique. Le temps d'exécution de l'algorithme est exponentiel en le nombre de séquences, ce qui est prévisible pour un problème NP-complet. Néanmoins, il est polynomial pour un nombre de séquences fixé.