当我们在一个 10000 多行的文件里头修改了 20 行代码，然后我们输入一行 git diff 去和某一个分支比较，到底用了什么方法来保证不会因为这一个 diff 让电脑卡死呢？

因为大部分的 diff，本质上就是以行为单位的 LCS。

Longest Common Subsequences（最长公共子序列）

在这里我们只讨论序列长度确定的情况下的解法。

LSD 问题例子：有 OPABIZCA 和 OPIABZCD 则 OPABZ 为这两组字符串的最长公共子串。

PS: 连续字符串不是必要条件，只要字符出现顺序相同即可。

如果我们的解法是暴力求解，然后和另一个字符串做匹配，复杂度就会是 O(KL^2)

如果我们构建矩阵来存储动态规划过程中子问题的解，则复杂度就会大大优化。

话不多说，上代码来解说。

x = ["b", "d", "a", "c", "z", "b", "d"]
y = ["b", "d", "b", "c", "b", "x", "d", "a"]
#在这一步已知结果应该是 bdcbd 让我们往下反推

5.times {|char| y << chars[rand(26)]}
c = Array.new(x.size + 1){Array.new(y.size + 1, 0)}
b = Array.new(x.size + 1){Array.new(y.size + 1, 0)}

def LCS_length(x, y, c, b)
  (1..x.size).each do |i|
    (1..y.size).each do |j|
      if x[i - 1] == y[j - 1]
        # 如果相等，把c 数组的i,j 位置设置为斜上方的值 + 1
        # b 数组的对应位置为 0
        c[i][j] = c[i - 1][j - 1] + 1
        b[i][j] = 0
      else
        if c[i - 1][j] >= c[i][j - 1]
          # 如果不相等而且前一个数更大，那么说明前面正在维护一个子串(有匹配的部分)
          c[i][j] = c[i - 1][j]
          b[i][j] = 1
        else
          # 如果没有，说明x字符串在这个坐标前部分没有匹配的必要
          c[i][j] = c[i][j - 1]
          b[i][j] = 2
        end
      end
    end
  end
end
def Print_LCS(x, b, i, j)
  return if i == 0 || j == 0
  if b[i][j] == 0
    Print_LCS(x, b, i - 1, j - 1)
    printf("%c ", x[i - 1])
  elsif(b[i][j] == 1)
    Print_LCS(x, b, i - 1, j)
  else
    Print_LCS(x, b, i, j - 1)
  end
end



LCS_length(x, y, c, b)

构建完之后得到两个矩阵 c,b

# 最后执行递归函数从后往前比较矩阵来获得我们需要的字符串
Print_LCS(x, b, x.size, y.size)

1. 本文的无码版 https://gist.github.com/Madao-3/caa6bc78d7876fd1917b69b3b0aad007
2. 推荐一个 gem 包 https://github.com/halostatue/diff-lcs
3. JGit 的 Diff 的实现代码 https://github.com/eclipse/jgit/blob/ebfd62433a58d23af221adfdffed56d9274f4268/org.eclipse.jgit/src/org/eclipse/jgit/diff/HistogramDiff.java

思考题：事实上，React 最值得称道的优点之一，就是他的 Virtual DOM Diff 优化，请问：「它做了哪些优化？」