I am writing a program that computes and displays diffs. I implemented Meyers algorithm that computes the LCS between 2 subsequences (
seq2); its output is one of the possible LCS and a partition of
seq2, one projection of which is
I want to improve it so that the LCS displayed minimizes the number of breaks; to do so, I implemented a function
seqis a sequence of characters
lcsis a subsequence of
- the output is a partition of
p0, p1, p2, ... pnsuch as
p0 + p2 +or
p1 + p3 + ...is
I did so using some sort of BFS, at each step finding the next element non-covered in
seq and greedily expanding the common part.
The resulting algorithm is quite slow: on a typical input, ~3x slower that the Myers algorithm which seems to compute something way more complex. See code here: https://github.com/mookid/diffr/blob/c9ed7746193fd9833ddce1237d6e5005e91deaf4/diffr-lib/src/best_projection.rs
Am I missing a better algorithm?