最长公共子序列

维基百科,自由的百科全书
跳转至: 导航搜索

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

定義[编辑]

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

複雜度[编辑]

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

解法[编辑]

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

设有二维数组 f[i][j] 表示 Xi 位和 Yj 位之前的最长公共子序列的长度,则有:

f[1][1] = same(1,1)
f[i][j] = max\{f[i-1][j-1] + same(i,j), f[i-1][j],f[i][j-1]\}

其中,same(a,b)X 的第 a 位与 Y 的第 b 位完全相同时为“1”,否则为“0”。

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

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

外部連結[编辑]