Algorithms and Data Structures · Senior · Question 36 of 75
Which algorithm do git diff and many diff tools use by default?
- 1Dijkstra's algorithm on a graph of lines
- 2Levenshtein distance computed per character
- ✓Correct answer: Myers' algorithm, based on the shortest edit script
Explanation
Myers finds the shortest sequence of insertions and deletions in O((n + m) × d), where d is the number of differences, so similar files diff quickly. It's closely related to the longest common subsequence.