最长公共子序列(LCS)

定义

最长公共子序列(Longest Common Subsequence, LCS)问题是找出两个序列共有的、保持原有相对顺序但不要求连续的最长子序列。它与要求连续的最长公共子串是不同问题。

算法

标准解法为动态规划:dp[i][j] 表示第一个序列前 i 项与第二个序列前 j 项的 LCS 长度。当前元素相等时 dp[i][j] = dp[i-1][j-1]+1,否则取 dp[i-1][j] 与 dp[i][j-1] 的较大者。时间复杂度 O(mn);通过记录转移方向可回溯出具体子序列。Hunt-Szymanski 等算法在匹配点稀疏时更快。

应用

diff 与版本控制系统计算文件差异(Git 的差异展示)、生物信息学序列相似性分析、抄袭检测、数据同步与合并冲突判定等。

说明

一般情形下 LCS 无法显著快于二次时间,这是细粒度复杂度理论中的著名结论之一。