What we see depends mainly on what we look for. John Lubbock We do not see things as they are, we see things as we are. Anais Nin Gestalt Diffing algorithm in Java Intro When it comes down to diffing or LCS usually story ends with Myers algorithm. It is idea to create BitMatrix (or IntMatrix) of similarities between two strings and then to approach to a problem from graph point, and find the shortest path of changes between two arrays. It sounds as a great solution, and it is, but in reality it has few drawbacks. It is algorithm that gives great results most of the time but it is a slow algorithm for some obvious cases, if strings are equal, or very similar. You create whole matrix but for your solution not all values from matrix are needed. It involves one more algorithm, finding the shortest path in it self. Then improvements of Myers algorithm came, like to check on start are strings are equals, to check for same prefix or suffix, to run snake chase from both...
Sasa Jovancic, private blog