I have trimmed down the memory usable a little but, but not reduce the space complexity. (Reduced by 80 % on 32-bit machines, and 88.(8) % on 64-bit machines, as the supreium.)
If I understood that algorithm correct, I do not think it will produce the optimal result (I have not look in to it tough.) But it would its time complexity would be favourable for ridiculously large files. Some UNIX-like systems have bdiff, comparing really large files. Perhaps sbase should have diff using the algorithm based on the Wagner–Fischer algorithm for optimal result, and bdiff using the algorithm you described for optimal complexities.
pgpgRS99qxcPW.pgp
Description: OpenPGP digital signature
