最长公共子序列

✍ dations ◷ 2025-09-19 03:08:38 #算法,动态规划,组合数学,多项式时间问题,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

相关

  • 蝴蝶梦《蝴蝶梦》(英语:Rebecca)是一部由希区柯克所导演的黑白悬疑电影,改编自女作家达夫妮·莫里哀的同名小说,劳伦斯·奥利维尔和琼·芳登主演。这是希区柯克来到好莱坞以后所拍摄的
  • 莪相莪相(Ossian)是传说中3世纪时爱尔兰英雄,吟游诗人;被指为1760年起苏格兰诗人詹姆斯·麦佛森 (James Macpherson) 发表一系列史诗的作者。当代评论家对于作品真实性的看法有分歧
  • 外贸依存度贸易依存度(foreign trade degree of dependence, FTD)是指一定时期内一国或一地区的进出口贸易值与该国或该地区同时期内的国内生产总值(GDP)的比值,即E X
  • 自循环解释器自循环解释器(英语:Meta-circular evaluator)是元解释器(Metainterpreter,或Self-interpreter)的一种。自循环解释器不仅是在解释型语言中写成(如Scheme的自循环解释器是在Scheme中
  • 生命之柱主教座堂生命之柱主教座堂(格鲁吉亚语:სვეტიცხოვლის საკათედრო ტაძარი)是位于乔治亚东部的一座乔治亚正教会主教座堂。生命之柱主教座堂是乔治亚最重要的教
  • 林钦尼亚木·阿玛尔扎尔嘎勒林钦尼亚木·阿玛尔扎尔嘎勒(Rinchinnyamiin Amarjargal)(1961年-)生于乌兰巴托,他是蒙古民族进步党和民族民主党创始人之一,1999年7月30日至2000年7月26日任蒙古总理。
  • 先烈路 (广州)先烈路位于中国广州市,为一条呈东北至西南走向的主干道。其西南起东风东路,东北接禺东西路,全长3670米,宽约33米,分东、中、南三段。先烈路原名东沙马路,寓意由大东门外至沙河。马
  • 塞拉潘·纳丹塞拉潘·拉马·纳丹(英语:Sellapan Ramanathan,通称S R Nathan;泰米尔语:செல்லப்பன் ராமநாதன்,通称S R நாதன்;1924年7月3日-2016年8月22日)新加坡泰米尔裔政
  • 白翅交嘴雀白翅交嘴雀(学名:)为雀科交嘴雀属的鸟类。分布于欧洲、阿拉斯加、加拿大、俄罗斯、日本以及中国大陆的东北、华北等地,多见于山区森林鸟类、多栖于山地针叶林以及也见于针阔混交
  • 东城坊镇东城坊镇,是中华人民共和国河北省保定市涿州市下辖的一个乡镇级行政单位。东城坊镇下辖以下地区:东城坊村、西城坊村、马踏营村、宋家营村、西疃村、郝家庄村、三城村、二站村