Plus longue sous-séquence commune

Un article de Wikipédia, l'encyclopédie libre.
Cet article est une ébauche concernant l’informatique.
Vous pouvez partager vos connaissances en l’améliorant. (Comment ?).

La détermination de la plus longue sous-séquence commune à différentes (super-) séquences et 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.

[modifier] Informatique

Du fait de son caractère NP-complet, il est possible de proposer un algorithme de résolution de ce problème. Un tel algorithme est généralement basé sur les principes de programmation dynamique.