Speeds up LCS algorithm for well-separated sections of change
By exploiting unique matches between the two files, it is possible to
"restart" the LCS algorithm at times and reset the buildup of square
computational complexity.
* subversion/libsvn_diff/lcs.c
(svn_diff__snake_t): Added uniquematchcount member.
(svn_diff__snake): Increments uniquematchcount each time
a matching token occurs only once in each file.
(clear_fp): New function that removes nonviable states.
(svn_diff__lcs): Restarts LCS algorithm from p=0 if the number
of unique matches exceeds the number of mismatches, using
the first state where that occurs as the new start state.
git-svn-id: https://svn.apache.org/repos/asf/subversion/branches/diff-improvements@1140247 13f79535-47bb-0310-9956-ffa450edef68
1 file changed
