LCS

Idee: die beiden Aufgaben sind äquivalent:

• kürzeste Edit-Sequenz finden
• längste gemeinsame Teilfolge (longest common subsequence) finden

Beispiel: y = AB$\fbox{\ensuremath{C}}\fbox{\ensuremath{AB}}B\fbox{\ensuremath{A}}, z = \fbox{\ensuremath{C}}B\fbox{\ensuremath{AB}}\fbox{\ensuremath{A}}C$

für x = CABA gilt x≤y und x≤z,

wobei die Relation ≤ auf Σ^* so definiert ist:

u≤v, falls man u aus v durch Löschen einiger Buchstaben erhält (jedoch ohne die Reihenfolge der übrigen Buchstaben zu ändern)

vgl. mit Ausgabe von git diff <commit-1> <commit-2>