Overview
La Plus Longue Sous-séquence Commune (LCS) trouve la sous-séquence la plus longue commune à deux chaînes (sans nécessiter de contiguïté).
Analogy
Comme trouver les auteurs que deux listes de lecture ont en commun, dans le même ordre.
Step-by-step
- Crée un tableau 2D dp[i][j]
- Si s1[i-1]==s2[j-1] : dp[i][j] = dp[i-1][j-1] + 1
- Sinon : dp[i][j] = max(dp[i-1][j], dp[i][j-1])
- Longueur = dp[m][n]
Visual
ABCBDAB vs BDCAB
dp[3][3]=2 (BC)
→ LCS = BCAB (longueur 4)
Common mistakes
- Confondre sous-séquence (non contiguë) avec sous-chaîne (contiguë)
- Reconstruction incorrecte de la LCS depuis le tableau DP
Practice questions
- Trouve la LCS de deux chaînes
- Étends pour trouver la longueur de la plus longue sous-chaîne commune
Space
O(m × n) ou O(min(m,n))