最长的公共子序列

最长的公共子序列 (LCS) 问题是找到 一组序列中的所有序列 共有的 最长子序列 (通常仅两个序列) 的问题. 它不同于最常见的子串问题: 与子串不同,子序列不需要占据 原始序列中的连续位置.

• 1. a1b2c3
• 2. 123
• LCS : 123

应用

最长的公共子序列 问题是 典型的计算机科学问题,数据比较 程序的基础,例如 差异的实用程序,应用于生物信息学. 它还广泛用于诸如 Git之类 的修订控制系统,用于协调 对 修订控制的文件集合 所做的 多个更改.

DNA 的 序列

例

• 输入序列ABCDGH和AEDFHR , LCS 是ADH长度3.
• 输入序列AGGTAB和GXTXAYB , LCS 是GTAB长度为4.

参考

• Wikipedia
• YouTube