经常使用git diff 但是其是如何实现的呢？
本博客简单实现不考虑行的比较。可以比较两个字符串

// 相当于把每一行换比较换成字符比较，道理一样
s1='xxxxxxxxxx'
s2='yyyyyyyyyy'

首先我们把文件转化为两个列表，列表的每个元素是文件的某一行：

A = [1行、2行、3行、4行、…]
B = [1行、2行、3行、4行、…]
然后我们计算A和B最长的相似元素的长度lcs（递归就是力量）

lcs = (A, B) ->
result = 0
if A.length is 0 or B.length is 0
result
else if A[0] is B[0]
result = 1 + lcs(A[1..], B[1..])
else
result = Math.max(lcs(A, B[1..]), lcs(A[1..], B))
(真实环境下，文件足够大的话，会因为递归太多而爆栈……）

拿到了lcs，然后根据计算lcs时找到的能对上的头，就可以得出两个文件最大的相同部分，用C表示，那么，A、B就被切分成了：

A-、C、A+
B-、C、B+

然后，我们再用同样的方法比较A-、B-，以及A+、B+，一直这样递归下去，一段段地比较，最后把所有的结果拼起来。

最后使用Java实现

public class LCSTest {public static class Node {int st;String subTpl;int length;int op;public Node(int st, int length, int op) {this.st = st;this.length = length;this.op = op;}public Node(int st, int length, int op, String subTpl) {this.length = length;this.op = op;this.st = st;this.subTpl = subTpl;}@Override public String toString() {return "Node{" +"length=" + length +", st=" + st +", op=" + op +'}';}}// 下标都是偏移+1// 1是相同 2 是多了 3 是少了public static List<Node> LCS(String tpl, String str, int strSt) {if (tpl.length() == 0 && str.length() == 0) {return new ArrayList<>();} else if (tpl.length() == 0) {return new ArrayList<>(Collections.singletonList(new Node(strSt, str.length(), 2)));} else if (str.length() == 0) {return new ArrayList<>(Collections.singletonList(new Node(strSt, tpl.length(), 3, tpl)));}int[][] dp = new int[tpl.length() + 1][str.length() + 1];int maxi, maxj, maxk;maxi = maxj = maxk = 0;for (int i = 1; i <= tpl.length(); i++) {for (int j = 1; j <= str.length(); j++) {if (tpl.charAt(i - 1) == str.charAt(j - 1)) {dp[i][j] = dp[i - 1][j - 1] + 1;if (dp[i][j] >= maxk) {maxk = dp[i][j];maxi = i;maxj = j;}}}}List<Node> list = new ArrayList<>();if (maxk == 0) {list.add(new Node(strSt, tpl.length(), 3, tpl));list.add(new Node(strSt, str.length(), 2));} else {list.addAll(LCS(tpl.substring(0, maxi - maxk), str.substring(0, maxj - maxk), strSt));list.add(new Node(maxj - maxk, maxk, 1));list.addAll(LCS(tpl.substring(maxi, tpl.length()), str.substring(maxj, str.length()), maxj));}return list;}public static void main(String args[]) {String tpl = "【#company#】您的验证码是#code#";String str = "你好【啊啊啊】您的验证码是123";List<Node> list = LCS(tpl, str, 0);for (Node node : list) {if (node.op == 1) {System.out.println("sam:" + str.substring(node.st, node.st + node.length));} else if (node.op == 2) {System.out.println("add:" + str.substring(node.st, node.st + node.length));} else if (node.op == 3) {System.out.println("sub:" + node.subTpl);}}}
}