最长公共子序列

✍ dations ◷ 2025-07-02 12:27:30 #算法,动态规划,组合数学,多项式时间问题,NP完全问题

最长公共子序列(LCS)是一个在一个序列集合中(通常为两个序列)用来查找所有序列中最长子序列的问题。这与查找最长公共子串的问题不同的地方是:子序列不需要在原序列中占用连续的位置 。最长公共子序列问题是一个经典的计算机科学问题,也是数据比较(英语:data comparison)程序,比如Diff工具,和生物信息学应用的基础。它也被广泛地应用在版本控制,比如Git用来调和文件之间的改变。

一个数列 S {\displaystyle S} ,如果分别是两个或多个已知数列的子序列,且是所有符合此条件序列中最长的,则 S {\displaystyle S} 称为已知序列的最长公共子序列。

对于一般性的LCS问题(即任意数量的序列)是属于NP-hard。但当序列的数量确定时,问题可以使用动态规划(Dynamic Programming)在多项式时间内解决。

最长公共子序列问题存在最优子结构:这个问题可以分解成更小,更简单的“子问题”,这个子问题可以分成更多的子问题,因此整个问题就变得简单了。最长公共子序列问题的子问题的解是可以重复使用的,也就是说,更高级别的子问题通常会重用低级子问题的解。拥有这个两个属性的问题可以使用动态规划算法来解决,这样子问题的解就可以被储存起来,而不用重复计算。这个过程需要在一个表中储存同一级别的子问题的解,因此这个解可以被更高级的子问题使用。

动态规划的一个计算最长公共子序列的方法如下,以两个序列 X {\displaystyle X} Y {\displaystyle Y} 为例子:

设有二维数组 f {\displaystyle f} 表示 X {\displaystyle X} i {\displaystyle i} 位和 Y {\displaystyle Y} j {\displaystyle j} 位之前的最长公共子序列的长度,则有:

其中, s a m e ( a , b ) {\displaystyle same(a,b)} X {\displaystyle X} 的第 a {\displaystyle a} 位与 Y {\displaystyle Y} 的第 b {\displaystyle b} 位完全相同时为“1”,否则为“0”。

此时, f {\displaystyle f} 中最大的数便是 X {\displaystyle X} Y {\displaystyle Y} 的最长公共子序列的长度,依据该数组回溯,便可找出最长公共子序列。

该算法的空间、时间复杂度均为 O ( n 2 ) {\displaystyle O(n^{2})} ,经过优化后,空间复杂度可为 O ( n ) {\displaystyle O(n)}


下面算法计算了所有子问题的最长公共子序列长度C

相关

  • 四级立体结构蛋白质四级结构(英语:Protein quaternary structure)是生物化学中用于描述多亚基蛋白质复合物中各个折叠蛋白质亚基的排列组合。许多蛋白质实际上是多个多肽链的组装。 四级结
  • 3β-雄烷二醇3β-雄烷二醇(英语:3β-Androstanediol,缩写3β-diol,全称5α-雄烷-3β,17β-二醇,5α-androstane-3β,17β-diol)是一种内源性的甾体激素,有较强的雌激素活性。3β-雄烷二醇可由脱
  • 脓疡脓疡(拉丁语:abscessus; 德语:Abszess; 法语:Abcès; 英语:Abscess)又称作脓疮、脓肿。指的是在身体组织中蓄积的脓。接近体表的脓疡会有红、肿、热、痛等症状,触诊病灶时感觉其内
  • 化学肥料肥料是任一天然或合成的一种或多种植物成长发育所必需的营养元素,约30%~50%的作物产量增加是来归因于天然或无机化学合成的商业肥料。市面上出售的肥料种类及品牌极多,依成分
  • 燕麦甾醇(1R,2S,5S,7S,11R,14R,15R)-2,15-二甲基-14-四环-9-十七烯-5-醇燕麦甾醇(英语:Avenasterol,或称为δ-7-燕麦甾醇,或豆甾-7,24Z-二烯-3β-醇)是一种天然的豆甾烷型植物固醇,最早在
  • 补骨脂补骨脂(学名:Psoralea corylifolia),又名破故纸,为豆科补骨脂属下的一个种。夏天的时候,会开白色或者淡紫色的花儿。这种草的种子可以做药。
  • 鹈形目鹈形目(学名:Pelecaniformes)在动物分类学上是鸟纲中的一个目,包括6个科。
  • 伊戈尔·晓戈列夫伊戈尔·奥列格维奇·晓戈列夫(俄语:Игорь Олегович Щёголев,1965年11月10日-),俄罗斯联邦政治人物。现任俄罗斯联邦总统驻中央联邦管区全权代表。1965年生于
  • 丁香茄丁香茄(学名:)是旋花科番薯属的植物。分布在热带非洲、墨西哥、菲律宾、越南、印度、日本、缅甸、南美洲、锡金以及中国大陆的河南、湖南、云南、湖北等地,生长于海拔580米至1,2
  • 水泉 (作家)水泉(1986年12月30日-),台湾奇幻作家,本名苏嘉敏,于就读台北市立松山高级中学时完成共五部的奇幻文学作品《风动鸣》而受到注意,辅仁大学哲学系毕业。2004年,水泉以当时最年轻(16岁)作