Plus longue sous-séquence commune
concept en informatique théorique / De Wikipedia, l'encyclopédie encyclopedia
Cher Wikiwand IA, Faisons court en répondant simplement à ces questions clés :
Pouvez-vous énumérer les principaux faits et statistiques sur Plus longue sous-séquence commune?
Résumez cet article pour un enfant de 10 ans
AFFICHER TOUTES LES QUESTIONS
Ne doit pas être confondu avec plus longue sous-chaîne commune.
En informatique théorique, la plus longue sous-séquence commune à deux suites, ou deux chaînes de caractères, est une sous-suite extraite des deux suites, et de taille maximum. La résolution de ce problème peut être obtenue par programmation dynamique.
La généralisation à un nombre arbitraire de suites est un problème NP-difficile[1] : le temps d'exécution de tout algorithme est exponentiel en le nombre de séquences.