Liens entre LCS et SES

Étant données deux suites A et B, les deux problèmes d'énoncent :
SES
Trouver le plus petit edit script rendant compte des différences entre A et B. La taille d'un edit script est le nombre total de suppressions et d'insertions élémentaires qu'il décrit. Les instructions de changements (n,mci,k) coûtent la somme des suppressions et insertions qu'elles impliquent (soit n-m+k-i+2).
LCS
Trouver une plus longue sous-suite commune à A et B. On note A(i) le ième élément de la suite A. Une sous-suite de A est une suite C telle que C(i)=A(i+k(i)) et k est croissante.

À chaque edit script minimal correspond une unique sous-suite maximale, et on peut trouver un edit script minimal correspondant à chaque sous-suite minimale

Soit a la taille de A, et b la taille de B. Soit n la plus grande longueur possible des sous-suites communes. Soit k la longueur minimale des edit script décrivant toutes les différences entre A et B.

Supposons qu'on ait un edit script minimal. Soit C la suite des éléments de A qui n'est pas touchée par l'edit script. C est une sous-suite de A. C est aussi une sous-suite de B, car sinon l'edit script ne décrit pas toutes les différences entre A et B. Comme l'edit script est minimal, chaque élément de A et de B n'est touché au plus qu'une fois, donc la longueur de C est (a+b-k)/2. Si C n'est pas maximale, on a n>(a+b-k)/2

Soit maintenant D une sous-suite commune à A et à B de longueur maximale. On définit l'edit script qui enlève tous les éléments de A qui ne sont pas dans D, et rajoute tous les éléments de B qui ne sont pas dans D (de telle sorte qu'ils se retrouvent à la bonne place pour donner B). Le coût de cet edit script est a+b-2n. Donc si cet edit script n'est pas minimal, k<a+b-2n.

On en déduit que C est maximal, que le deuxième edit script est minimal, et que k=a+b-2n.