zhe.inkLongest 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
苏公网安备
32050902101537号