最长公共子序列

最长公共子序列（Longest Common Subsequence，简称LCS）是计算机科学中一个重要的字符串算法，用于寻找两个或多个序列共有的最长子序列。与子串不同，子序列不要求连续，但必须保持相对顺序。该算法在生物信息学（如DNA序列比对）、版本控制系统（如Git差异比较）和自然语言处理等领域有广泛应用。

定义与基本概念[编辑 | 编辑源代码]

给定两个序列 $X = (x_{1}, x_{2}, \dots, x_{m})$ 和 $Y = (y_{1}, y_{2}, \dots, y_{n})$ ，若存在严格递增的下标序列 $(i_{1}, i_{2}, \dots, i_{k})$ 和 $(j_{1}, j_{2}, \dots, j_{k})$ 使得对所有 $1 \leq t \leq k$ 有 $x_{i_{t}} = y_{j_{t}}$ ，则称 $Z = (z_{1}, z_{2}, \dots, z_{k})$ 是 $X$ 和 $Y$ 的公共子序列。LCS是其中最长的子序列。

示例[编辑 | 编辑源代码]

设 解析失败 (语法错误): {\displaystyle X = \text{"ABCBDAB"}} ，解析失败 (语法错误): {\displaystyle Y = \text{"BDCABA"}} ，则它们的LCS为 解析失败 (语法错误): {\displaystyle \text{"BCBA"}} 或 解析失败 (语法错误): {\displaystyle \text{"BDAB"}} （长度均为4）。

动态规划解法[编辑 | 编辑源代码]

LCS问题通常通过动态规划（Dynamic Programming）解决。定义二维数组 $d p [i] [j]$ 表示 $X$ 前 $i$ 个字符和 $Y$ 前 $j$ 个字符的LCS长度。状态转移方程如下：

$d p [i] [j] = {\begin{cases} 0 & 若 i = 0 或 j = 0, \\ d p [i - 1] [j - 1] + 1 & 若 x_{i} = y_{j}, \\ \max (d p [i - 1] [j], d p [i] [j - 1]) & 否则 . \end{cases}$

代码实现[编辑 | 编辑源代码]

以下是Python实现：

def longest_common_subsequence(X, Y):
    m, n = len(X), len(Y)
    dp = [[0] * (n + 1) for _ in range(m + 1)]
    
    for i in range(1, m + 1):
        for j in range(1, n + 1):
            if X[i-1] == Y[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
    lcs = []
    i, j = m, n
    while i > 0 and j > 0:
        if X[i-1] == Y[j-1]:
            lcs.append(X[i-1])
            i -= 1
            j -= 1
        elif dp[i-1][j] > dp[i][j-1]:
            i -= 1
        else:
            j -= 1
    return ''.join(reversed(lcs))

# 示例
X = "ABCBDAB"
Y = "BDCABA"
print(longest_common_subsequence(X, Y))  # 输出: "BDAB"

复杂度分析[编辑 | 编辑源代码]

时间复杂度： $O (m n)$ （填充DP表）
空间复杂度： $O (m n)$ （可优化至 $O (\min (m, n))$ ）

可视化示例[编辑 | 编辑源代码]

实际应用案例[编辑 | 编辑源代码]

1. 生物信息学：比对DNA序列时，LCS用于识别保守区域。 2. 版本控制：Git的差异比较工具利用LCS算法生成文件变更记录。 3. 拼写检查：通过LCS计算编辑距离，建议最接近的正确单词。

变体与扩展[编辑 | 编辑源代码]

最长公共子串（要求连续）
多序列LCS（扩展到多个序列）
带权LCS（字符匹配赋予不同权重）

练习建议[编辑 | 编辑源代码]

1. 手动计算 解析失败 (语法错误): {\displaystyle X = \text{"AGGTAB"}} 和 解析失败 (语法错误): {\displaystyle Y = \text{"GXTXAYB"}} 的LCS。 2. 尝试优化空间复杂度至 $O (n)$ 。 3. 实现多序列LCS的启发式算法。

总结[编辑 | 编辑源代码]

LCS是字符串处理中的基础算法，通过动态规划高效解决。理解其原理后，可进一步探索后缀自动机等高级优化方法。