Article on other languages:
- Longest_common_subsequence_problem
- 최장_공통_부분_수열
- Najdłuższy_wspólny_podciąg
- Наибольшая_общая_подпоследовательность
- 最长公共子序列
 |
del.icio.us |
 |
Digg |
 |
Furl |
 |
|
 |
Rojo |
| Add to OnlyWire |
 |
Cet article est une ébauche concernant l’informatique.
Vous pouvez partager vos connaissances en l’améliorant (comment ?) selon les recommandations des projets correspondants.
|
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.
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.
