Plus Longue Sous-séquence Commune (LCS)
Algorithmique classique
Enonce
Calculer la longueur de la plus longue sous-séquence commune (LCS) entre deux chaînes a et b.
Signature attendue
def lcs(a: str, b: str) -> int:Exemples
lcs("ABCBDAB", "BDCAB")→4 (BCAB)lcs("abc", "def")→0lcs("python", "pthon")→5
📖 Rappel de cours
Si les caractères courants coïncident, la longueur augmente de 1 et on avance dans les deux chaînes ; sinon on garde le meilleur des deux avancées possibles.
⚠ Le piège : Une sous-séquence n'est pas une sous-chaîne : ses caractères ne sont pas forcément consécutifs. « ace » est une sous-séquence de « abcde ».
← Exercices Python pour la prépa — CPGE scientifique et ECG
Exercices du meme theme
- Somme des Sous-ensembles
- Fibonacci par Programmation Dynamique
- Sac à Dos 0/1
- Distance d'Édition (Levenshtein)
- Montée d'Escalier
- Recherche Dichotomique Itérative
La correction commentee, les indices progressifs, l'execution du code dans le navigateur et la verification par l'IA sont reserves aux abonnes.