当前位置：首页 > Go > 正文

Go语言实现最长公共子序列（LCS）

主机测评网
Go
2025-12-25
164

在计算机科学中，最长公共子序列（Longest Common Subsequence，简称LCS）是一个经典问题，广泛应用于生物信息学、版本控制系统（如 Git 的 diff 功能）、文本比对等领域。本文将使用 Go语言 从基础概念出发，手把手教你实现 LCS 算法，即使你是编程小白也能轻松理解！

什么是“子序列”？

首先，我们要区分“子串”和“子序列”：

子串：必须是连续的字符序列。例如，"abc" 的子串包括 "ab"、"bc"。
子序列：不要求连续，但必须保持原有顺序。例如，"abc" 的子序列包括 "ac"、"b"、"abc" 等。

因此，最长公共子序列 就是在两个字符串中都出现的、长度最长的子序列。

举个例子

假设我们有两个字符串：

字符串 A："ABCDGH"
字符串 B："AEDFHR"

它们的最长公共子序列是 "ADH"，长度为 3。

Go语言实现最长公共子序列（LCS） Go语言最长公共子序列 LCS算法实现动态规划Go教程字符串匹配算法第1张

为什么用动态规划？

暴力枚举所有子序列的时间复杂度太高（指数级），而 动态规划（Dynamic Programming）可以高效地解决这个问题，时间复杂度为 O(m×n)，其中 m 和 n 分别是两个字符串的长度。

Go语言实现 LCS 算法

我们将分两步实现：

计算 LCS 的长度
回溯构造 LCS 字符串本身

第一步：构建 DP 表格

我们创建一个二维数组 dp[i][j]，表示字符串 A 的前 i 个字符与字符串 B 的前 j 个字符的 LCS 长度。

package mainimport "fmt"// 计算两个字符串的 LCS 长度func lcsLength(s1, s2 string) int {    m, n := len(s1), len(s2)    // 创建 (m+1) x (n+1) 的 DP 表    dp := make([][]int, m+1)    for i := range dp {        dp[i] = make([]int, n+1)    }    // 填充 DP 表    for i := 1; i <= m; i++ {        for j := 1; j <= n; j++ {            if s1[i-1] == s2[j-1] {                dp[i][j] = dp[i-1][j-1] + 1            } else {                dp[i][j] = max(dp[i-1][j], dp[i][j-1])            }        }    }    return dp[m][n]}func max(a, b int) int {    if a > b {        return a    }    return b}func main() {    str1 := "ABCDGH"    str2 := "AEDFHR"    fmt.Printf("LCS 长度: %d\n", lcsLength(str1, str2))}

第二步：回溯构造 LCS 字符串

有了 DP 表后，我们可以从右下角开始回溯，重建 LCS 字符串。

// 构造 LCS 字符串func buildLCS(s1, s2 string) string {    m, n := len(s1), len(s2)    dp := make([][]int, m+1)    for i := range dp {        dp[i] = make([]int, n+1)    }    // 先填充 DP 表    for i := 1; i <= m; i++ {        for j := 1; j <= n; j++ {            if s1[i-1] == s2[j-1] {                dp[i][j] = dp[i-1][j-1] + 1            } else {                dp[i][j] = max(dp[i-1][j], dp[i][j-1])            }        }    }    // 回溯构造 LCS    var lcs []byte    i, j := m, n    for i > 0 && j > 0 {        if s1[i-1] == s2[j-1] {            lcs = append(lcs, s1[i-1])            i--            j--        } else if dp[i-1][j] > dp[i][j-1] {            i--        } else {            j--        }    }    // 因为是从后往前构造，需要反转    for left, right := 0, len(lcs)-1; left < right; left, right = left+1, right-1 {        lcs[left], lcs[right] = lcs[right], lcs[left]    }    return string(lcs)}func main() {    str1 := "ABCDGH"    str2 := "AEDFHR"    result := buildLCS(str1, str2)    fmt.Printf("LCS 字符串: %s\n", result) // 输出: ADH}