查看“最长公共子序列”的源代码

{{NoteTA
|G1 = IT
}}
{{redirect2|LCS|美國海軍的一種軍艦類別|濒海战斗舰}}
{{Distinguish|最长公共子串}}

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

== 定義 ==
一个数列<math>S</math>，如果分别是两个或多个已知[[数列]]的子序列，且是所有符合此条件序列中最长的，则<math>S</math>称为已知序列的最长公共子序列。

== 複雜度 ==
對於一般性的LCS問題（即任意數量的序列）是屬於[[NP-hard]]。但當序列的數量確定時，問題可以使用[[动态规划]]（Dynamic Programming）在多項式時間内解決。<ref>{{cite book
 | last = 屈 | first = 婉玲
 | title = 算法设计与分析
 | year = 2011
 | publisher = 清华大学出版社
 | location = 北京清华大学学研大厦A座
 | page = 67
 | isbn = 978-7-302-24756-2
}}</ref>

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

[[动态规划]]的一个计算最长公共子序列的方法如下，以两个序列<math>X</math>、<math>Y</math>为例子：

设有二维数组<math>f[i][j]</math>表示<math>X</math>的<math>i</math>位和<math>Y</math>的<math>j</math>位之前的最长公共子序列的长度，则有：
:<math>f[1][1] = same(1,1)</math><br/>
:<math>f[i][j] = max\{f[i-1][j-1] + same(i,j), f[i-1][j],f[i][j-1]\}</math><br/>
其中，<math>same(a,b)</math>当<math>X</math>的第<math>a</math>位与<math>Y</math>的第<math>b</math>位完全相同时为“1”，否则为“0”。

此时，<math>f[i][j]</math>中最大的数便是<math>X</math>和<math>Y</math>的最长公共子序列的长度，依据该数组回溯，便可找出最长公共子序列。

该[[算法]]的空间、时间复杂度均为<math>O(n^{2})</math>，经过优化后，空间复杂度可为<math>O(n)</math>。

<!--
=== 前缀 ===
当串变得更短时，子问题就变得简单了。为此引进一个术语叫做“前缀”：一个串的前缀是把这个串的尾部去掉。让''S''代表串（AGCA），然后串（AG）是''S''的前缀。前缀用原来的串的名字来表示，并且带有一个下标来说明这个前缀包含了多少字符。<ref>{{cite book
 | last = Xia | first = Xuhua
 | title = Bioinformatics and the Cell:  Modern Computational Approaches in Genomics, Proteomics and Transcriptomics
 | year = 2007
 | publisher = Springer
 | location = New York
 | page = 24
 | isbn = 0-387-71336-0
}}</ref>我们可以用''S''<sub>2</sub>来表示前缀（AG），因为它包含了串''S''的前两个元素。串''S''可能含有的前缀是： 
:''S''<sub>1</sub> = (A)
:''S''<sub>2</sub> = (AG)
:''S''<sub>3</sub> = (AGC)
:''S''<sub>4</sub> = (AGCA).

为解决两个任意长度的最长公共字串问题，需要构造函数 ''LCS''(''X'', ''Y'') 返回''X''和''Y''最长的字串。这个函数满足以下两个特性：
-->

=== 计算LCS的长度 ===
下面算法计算了所有子问题的最长公共子序列长度<code>C[i,j]</code>。

 '''function''' LCSLength(X[1..m], Y[1..n])
     C = array(0..m, 0..n)
     '''for''' i := 0..m
        C[i,0] = 0
     '''for''' j := 0..n
        C[0,j] = 0
     '''for''' i := 1..m
         '''for''' j := 1..n
             '''if''' X[i] = Y[j]
                 C[i,j] := C[i-1,j-1] + 1
             '''else'''
                 C[i,j] := max(C[i,j-1], C[i-1,j])
     '''return''' C[m,n]

== 参见 ==
* [[莱文斯坦距离]]
* [[Floyd-Warshall算法]]
* [[维特比算法|Viterbi算法]]

== 引用 ==
{{reflist}}

== 外部連結 ==
* {{en}} [http://nist.gov/dads/HTML/longestCommonSubsequence.html longest common subsequence]
* {{en}} [http://www.ics.uci.edu/~eppstein/161/960229.html Longest Common Subsequences]

[[Category:算法]]
[[Category:动态规划]]
[[Category:组合数学]]
[[Category:多项式时间问题]]
[[Category:NP完全问题]]