A while ago I posted a PHP implementation of a diff algorithm I came up with. Since it was well received, and it’s a useful little algorithm to have, I created a Python version as well.
There are a few performance improvements as well. The PHP version creates an array in memory proportional to the square of the size of the input, while the Python version’s array is directly proportional to the size of the input. I also sped up how the algorithm finds the indexes of the “new” elements in the “old” array.
Update: As of 2009, the code is hosted on GitHub.