Just took a look at this code.  Looks nice, clean, elegant, and to the
point.   And a useful tool!  Nicely done.

I would find it useful if there were a pure-Python version of the code,
which would be used as a fallback wherever the extension module isn't
available.  Maybe you've tried this already and it's quite a bit slower? 
In any case I think it would be handy to have both versions for different
circumstances.  Let me know if you'd like help porting the LCS algorithm to
Python.

Incidentally, isn't the worst-case running time of the LCS algorithm O(n
m), not O(n^2 + m^2)?