编辑“︁最长公共子序列”︁

{{DISPLAYTITLE:最长公共子序列}}

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

== 定义与基本概念 ==
给定两个序列 <math>X = (x_1, x_2, \dots, x_m)</math> 和 <math>Y = (y_1, y_2, \dots, y_n)</math>，若存在严格递增的下标序列 <math>(i_1, i_2, \dots, i_k)</math> 和 <math>(j_1, j_2, \dots, j_k)</math> 使得对所有 <math>1 \leq t \leq k</math> 有 <math>x_{i_t} = y_{j_t}</math>，则称 <math>Z = (z_1, z_2, \dots, z_k)</math> 是 <math>X</math> 和 <math>Y</math> 的公共子序列。LCS是其中最长的子序列。

=== 示例 ===
设 <math>X = \text{"ABCBDAB"}</math>，<math>Y = \text{"BDCABA"}</math>，则它们的LCS为 <math>\text{"BCBA"}</math> 或 <math>\text{"BDAB"}</math>（长度均为4）。

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

<math>
dp[i][j] = 
\begin{cases} 
0 & \text{若 } i=0 \text{ 或 } j=0, \\
dp[i-1][j-1] + 1 & \text{若 } x_i = y_j, \\
\max(dp[i-1][j], dp[i][j-1]) & \text{否则}.
\end{cases}
</math>

=== 代码实现 ===
以下是Python实现：

<syntaxhighlight lang="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"
</syntaxhighlight>

=== 复杂度分析 ===
* 时间复杂度：<math>O(mn)</math>（填充DP表）
* 空间复杂度：<math>O(mn)</math>（可优化至 <math>O(\min(m, n))</math>）

== 可视化示例 ==
<mermaid>
graph TD
    A[初始化DP表] --> B[逐行填充]
    B --> C{字符匹配?}
    C -->|是| D[左上角值+1]
    C -->|否| E[取左或上最大值]
    D --> F[更新DP表]
    E --> F
    F --> G[回溯路径]
</mermaid>

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

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

== 练习建议 ==
1. 手动计算 <math>X = \text{"AGGTAB"}</math> 和 <math>Y = \text{"GXTXAYB"}</math> 的LCS。
2. 尝试优化空间复杂度至 <math>O(n)</math>。
3. 实现多序列LCS的启发式算法。

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

[[Category:计算机科学]]
[[Category:数据结构与算法]]
[[Category:字符串算法]]