问题可以简化，每一行的字符串可以看成一个值，问题简化为求解两个整型数组的连续序列问题。

初步搞定之：Windiff 原理初探, 采用动态规划算法找最优解，不考虑交叉情况。

Update1:
经实验证明，在文件非常长的时候此算法非常之慢。

比如10k个文件，这样就会有个10k x 10k的int数组，内存一次性耗掉有400M之多，计算量庞大无比到了难以承受的地步。

我监测了一下windiff，人家在100k大小的两个文件比较只用了一秒多，内存最多时不超过50M。

一定有更好的解法。

今天路上和朋友讨论一下，有以下几种思路：
1、贪心算法
2、贪心算法 ＋ 部分动态规划
3、被比较对象每行的重复率很低，这个信息可能会有用。

Update2:
使用思路1的分析以及程序基本完成，效果显著，详细分析与程序流程图参见文章：Windiff 原理初探(续1)

程序运行结果对比:
我用C++在WindowsXP下实现这个程序，AMD2500+/512内存，Release版，删除printf输出(这里只算分析时间）以后，对两个12万行的文本做diff跑了10秒不到。
我试了一下WinMerge，不算其界面操作时间（即只算到分析结束，他后来死翘翘了），应该在5秒之内
不过，好像Windiff更快，一秒都不到，结果我打开一看，丫好像全错了:(，各位可以试试看，将1, 2, 3, 4, 5, 6, 7, 8每个数字一行然后重复这些行直到10万行，另一个文件用1, 2, 2, 4, 6, 6, 5每个数字一行然后重复到10万行，反正我机器VS2005的Windiff分析结果飞快，结果是这两个文件没有一行相同 :o ，汗一个

有没有更好的方法？上文里面提到的想法里面，想法2会优化结果，速度可能反而会慢一些，想法3应该是值得考虑的因素。

程序代码（估计有许多小bug）：http://www.2maomao.com/blog/wp-content/uploads/mydiff.cpp.html