Longest Common Subsequences code

Cheuksan Edward Wang wang02139 at gmail.com
Sun Oct 29 08:05:56 GMT 2006

I'm looking for python code that implements Longest Common Subsequences
efficiently. Idealy, it should just implement the get_matching_blocks method
in SequenceMatcher in quadratic time and linear space. i.e. Hirschberg's
algorithm. Does any other python VCS have it? If anyone can give me some
pointers to some code, it can save me some time.

At the moment, the python difflib is using cubic time. Patience diff doesn't
have optimality guarantees if there are no unique lines.


Cheuksan Edward Wang
-------------- next part --------------
An HTML attachment was scrubbed...
URL: https://lists.ubuntu.com/archives/bazaar/attachments/20061029/074ea30e/attachment.htm 

More information about the bazaar mailing list