On 25.11.2015 12:26, M.M. wrote:
> On Wednesday, November 25, 2015 at 12:43:58 AM UTC+1, bartekltg wrote:
>> Też myślałem, że robi coś sprytniejszego, ale intenert pisał,
>> że tylko szuka najlepszego podciągu. Zmajstrowałem więc
>> dwa małe pliki i test wydaje się to potwierdzać.
>
> Też poszukałem troszkę. Znalazłem, że diff próbuje znaleźć ciąg wierszy,
> który wymaga minimalnej ilości skasowań i/lub insercji, aby odtworzyć
> oryginalny plik - coś w okolicy minimalnej odległości Levenshteina.


Przecież dokłądnie to napisałem ;>

> Czyli
> nie ma żadnej gwarancji że diff ma zaimplementowany NWP. Podobno od
> dawna ma zaimplementowany NWP z jakimiś udoskonaleniami.

odległości Levenshteina zakąłda skasowanie/dopisanie/substytucje.
NWP zakłada skasowanie/dopisanie.

Z tego co piszesz to jednak NWP.

Zmodyfikowana odległosć edycyjna (bez podstawienia)
d'(X,Y) = |X| + |Y| - 2|NWP(X,Y)|

pzdr
bartekltg