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