最长公共子序列

维基百科,自由的百科全书
跳转至: 导航搜索
Confusion grey.svg
提示:本条目的主题不是最长公共子串

最长公共子序列問題是尋找两个或多个已知数列最長的子序列。

定義[编辑]

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

複雜度[编辑]

對於一般性的LCS問題(即任意數量的序列)是屬於NP-hard。但當序列的數量確定時,問題可以使用动态规划(Dynamic Programming)在多項式時間解決。

解法[编辑]

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

设有二维数组表示位和位之前的最长公共子序列的长度,则有:



其中,的第位与的第位完全相同时为“1”,否则为“0”。

此时,中最大的数便是的最长公共子序列的长度,依据该数组回溯,便可找出最长公共子序列。

算法的空间、时间复杂度均为,经过优化后,空间复杂度可为

外部連結[编辑]