Note that you can use Algorithm::LCS to have the meat of the work done in XS (which should be quite a bit faster). I haven't used it yet and I probably should integrate it with Algorithm::Diff, so switching to it probably won't be a simple as it eventually will be.