How do text differencing applications work?

Question

How do applications like DiffMerge detect differences in text files, and how do they determine when a line is new, and not just on a different line than the file being checked against?

Is this something that is fairly easy to implement? Are there already libraries to do this?

Answer 1

Here's the paper that served as the basis for the UNIX command-line tool diff.