网上能搜索到论文, 但是... 求讲解
An O(ND) Difference Algorithm and Its Variations (1986)
An O(ND) Difference Algorithm and Its Variations∗
可以看一下LCS http://en.wikipedia.org/wiki/Longest_common_subsequence_problem
就是用了 @smlg 提到的LCS。我用伪CoffeeScript代码翻译下吧：
首先我们把文件old、new转化为两个列表，列表的每个元素是文件的某一行：
A = [1行、2行、3行、4行、...]
B = [1行、2行、3行、4行、...]
然后我们计算A和B最长的相似元素的长度lcs（递归就是力量）
lcs = (A, B) ->
result = 0
if A.length is 0 or B.length is 0
result
else if A[0] is B[0]
result = 1 + lcs(A[1..], B[1..])
else
result = Math.max(lcs(A, B[1..]), lcs(A[1..], B))
(之所以叫伪CoffeeScript,因为真实环境下，文件足够大的话，会因为递归太多而爆栈……）
拿到了lcs，然后根据计算lcs时找到的能对上的头，就可以得出两个文件最大的相同部分，用C表示，那么，A、B就被切分成了：
A-、C、A+
B-、C、B+
然后，我们再用同样的方法比较A-、B-，以及A+、B+，一直这样递归下去，一段段地比较，最后把所有的结果拼起来，diff就出炉啦~
当然，实际的算法肯定会有很多优化的，比如找lcs会用更高效的算法（动态规划什么的），中间结果的缓存等等。
还有一种diff算法是比较字与字的不同（比较适合于文档），其实也是一样的原理，只是把按行切割改成按单词或字符切割而已（当然，具体到某种语言，为了得出更有意义的结果，会有一些调整）。