【Myers Diff】【差异纯算法】文章差异 劲爆算法

Myers算法由Eugene W.Myers在1986年发表的一篇论文中提出，是一个能在大部分情况产生”最短的直观的“diff的一个算法。
”寻找最短的直观的diff”是一个非常模糊的问题，首先，我们需要把这个问题抽象为一个具体的数学问题，然后再来寻找算法解决。抽象的过程交给算法科学家了，抽象的结果是：寻找diff的过程可以被表示为图搜索
什么意思呢？还是以两个字符串，src=ABCABBA，dst=CBABAC为例，根据这两个字符串我们可以构造下面一张图，横轴是src内容，纵轴是dst内容，那么图中每一条从左上角到右下角的路径，都表示一个diff。向右表示删除，向下表示新增，对角线则表示原内容保持不动。