Longest Common Sub-sequence

最长公共子序列(LCS)是一个在一个序列集合中(通常为两个序列)用来查找所有序列中最长子序列的问题。一个数列 ，如果分别是两个或多个已知数列的子序列，且是所有符合此条件序列中最长的，则称为已知序列的最长公共子序列。
最长公共子序列问题是一个经典的计算机科学问题，也是数据比较程序，比如Diff工具，和生物信息学应用的基础。它也被广泛地应用在版本控制，比如Git用来调和文件之间的改变。


示例代码：

package main

import "fmt"

func max(a, b int) int {
	if a > b {
		return a
	}
	return b
}

func lcs(X string, Y string, m int, n int) int {
	if m == 0 || n == 0 {
		return 0
	}

	if X[m-1] == Y[n-1] {
		return 1 + lcs(X, Y, m-1, n-1)
	}

	return max(lcs(X, Y, m, n-1), lcs(X, Y, m-1, n))
}

func main() {
	X := "AGGTAB"
	Y := "GXTXAYB"
	m := len(X)
	n := len(Y)

	fmt.Println("Length of LCS is", lcs(X, Y, m, n))
}

输出：

Length of LCS is 4