Git 是怎样生成 diff 的：Myers 算法

[cj1128]

https://cjting.me/2017/05/13/how-git-generate-diff/

Git 是怎样生成 diff 的：Myers 算法

[rc452860]

十分感谢，这文章对我非常有帮助。

[breezeling]

非常感谢，讲得很接地气

[gattonero1052]

想了一个dp算法，非常简单，而且最差时间复杂度是和BFS相同的都是O(mn)，可以稍稍优化下空间到线性

dp[i][j] = dp[i-1][j-1] if exist diagonal else min(dp[i-1][j],dp[i][j-1])

盲猜一波Myers的变体是把行哈希了

[yanhaijing]

👍

[xxwwp]

很有用，正在找相关资料，写的很清晰

[caibiPro]

@gattonero1052 想了一个dp算法，非常简单，而且最差时间复杂度是和BFS相同的都是O(mn)，可以稍稍优化下空间到线性

dp[i][j] = dp[i-1][j-1] if exist diagonal else min(dp[i-1][j],dp[i][j-1])

盲猜一波Myers的变体是把行哈希了

@gattonero1052 想了一个dp算法，非常简单，而且最差时间复杂度是和BFS相同的都是O(mn)，可以稍稍优化下空间到线性

dp[i][j] = dp[i-1][j-1] if exist diagonal else min(dp[i-1][j],dp[i][j-1])

盲猜一波Myers的变体是把行哈希了

Myers论文里是用通过从左上角和右下角同时向中间遍历来寻找split point，从而实现分治的方法，因此把空间复杂度降到了线性，因为不用存储前序路径了

[mml237]

“使用上面存储的 v 字典（每个 d 对应一个这样的字典），从终点反向得出路径”，请问是怎么回溯的，没想明白