Un algorithme de LCS naif
Si vous êtes en panne d'inspiration, voici déjà un
algorithme naif pour calculer la plus grande sous-suite commune :
- LCS(a,b) :
- Si a ou b est vide, retourner vide
- Si a[0]==b[0]
- alors retourner la suite commencant par a[0] et
finissant par LCS(a+1,b+1)
- sinon retourner la plus grande des suites LCS(a,b+1) et LCS(a+1,b)
Une idee de preuve : si a[0]==b[0], alors on ne peut pas faire
mieux que mettre a[0] en téte de la sous-suite commune. Sinon, on
ne peut pas avoir à la fois a[0] et b[0] en tète de la
sous-suite. Donc la plus grande sous-suite va ètre soit la plus
grande sous-suite en éliminant b[0], soit la plus grande sous-suite
en éliminant a[0].
On peut faire plus efficace en temps et en espace...