Le Wikipedia toujours utile prétend que diff met en œuvre la plus longue sous-séquence commune.Quel est l'algorithme de linux diff -y?
Cela ne peut pas être ainsi. Diff, au moins en mode -y, a trois types de rapport: ajouter, supprimer et remplacer. LCS n'a aucun concept de «substitut».
Quel est l'algorithme de diff? J'ai des raisons de ne pas croire que c'est la distance de Levenshtein, mais j'ai peut-être mal analysé cela.
Une insertion et une suppression l'une à côté de l'autre ne peuvent-elles pas être considérées comme une substitution? –
Cela pourrait être la réponse. – bmargulies
Le code source correspondant utilise uniquement l'ajout et la suppression. On dirait que la plus longue sous-séquence commune à première vue ... (Voir http://git.savannah.gnu.org/cgit/diffutils.git/tree/src/analyze.c?id=fecd0079fe6e15b0f53bf953721d838d9099bf05) – mre